Abstract
An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the consecutive arcs have opposite directions. The forward antidirected trails are special antidirected trails which begin and end with forward arcs. A digraph D containing a forward antidirected (x, y)-trail for every choice of \(x,y\in V(D)\) is called antistrong. An antidirected trail which begins with a forward arc and ends with a backward arc is a forward-backward antidirected trail. For any \(x,y\in V(D)\), if digraph D has a forward antidirected (x, y)-trail or a forward-backward antidirected (x, y)-trail, then D is weakly-antistrong. A digraph is anti-Eulerian if it admits a closed anti-directed Euler trail. Let \(BC(Z_n, C)\) be a Bi-Circulant graph with \(n\ge 3\) and \(C=\{j_1, j_2, \ldots , j_{l}\}\), \(l\ge 2\). This paper shows that the number of connected components of \(BC(Z_n, C)\) is equal to \(gcd(j_1-j_l, \ldots , j_{l-1}-j_{l}, n)\). Based on the result, necessary and sufficient conditions are given to decide whether a circulant digraph is antistrong, weakly-antistrong or anti-Eulerian.
Similar content being viewed by others
Availability of data and materials
Not applicable.
References
Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2009)
Bang-Jensen, J., Bessy, S., Jackson, B., Kriesell, M.: Antistrong digraphs. J. Combin. Theory Ser. B 122, 68–90 (2017)
Chartrand, G., Gavlas, H., Schultz, M., Wall, C.: Anticonnected digraphs. Util. Math. 51, 41–54 (1997)
Dobson, E.: Connectivity of circulant digraphs. J. Graph Theory 10, 9–14 (1986)
Dobson, E.: On isomorphisms of circulant digraphs of bounded degree. Disc. Math. 308, 6047–6055 (2008)
Grünbaum, B.: Antidirected Hamiltonian paths in tournaments. J. Combin. Theory Ser. B 11, 249–257 (1971)
Hu, Y., Wei, Y.: Rainbow antistrong connection in tournaments. Graphs Comb. 37, 167–181 (2021)
Liang, X., Meng, J., Zhang, Z.: Super-connectivity and hyper-connectivity of vertex transitive bipartite graphs. Graphs Comb. 23, 309–314 (2007)
Lu, Z.: On the automorphism groups of bi-cayley graphs. Acta. Sci. Nat. Univ. Pekinensis. 39 (2003)
Meng, J., Huang, Q.: Isomorphisms of circulant diagaphs. Appl. Math. A J. Chin. Univ. 9, 405–409 (1994)
Park, J.H., Chwa, K.Y.: Recursive circulant : a new topology for multicomputers networks. Proceedings of the International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN). IEEE. 73-80 (1994)
Xu, M.: Introduction of Finite Groups II. Science Press, Beijing (1999)
Yuan, L., Meng, J., Sabir, E.: The antistrong property for special digraph families. Graphs Comb. 37, 2511–2519 (2021)
Zhang, B., Wu, B.: Anti-Eulerian digraphs. Appl. Math. Comput. 411, 126513 (2021)
Funding
The funding has been received form Natural Science Foundation of Xinjiang Province with Grant nos. 2020D04046, 2021D01C116.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The research is supported by NSFXJ (Nos. 2020D04046, 2021D01C116).
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Yuan, L., Meng, J. Necessary and Sufficient Conditions for Circulant Digraphs to be Antistrong, Weakly-Antistrong and Anti-Eulerian. Graphs and Combinatorics 39, 22 (2023). https://doi.org/10.1007/s00373-023-02620-4
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-023-02620-4