[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

Necessary and Sufficient Conditions for Circulant Digraphs to be Antistrong, Weakly-Antistrong and Anti-Eulerian

  • Original Paper
  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

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 (xy)-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 (xy)-trail or a forward-backward antidirected (xy)-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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1

Similar content being viewed by others

Availability of data and materials

Not applicable.

References

  1. Bang-Jensen, J., Gutin, G.: Digraphs: Theory, Algorithms and Applications, 2nd edn. Springer, London (2009)

    Book  MATH  Google Scholar 

  2. Bang-Jensen, J., Bessy, S., Jackson, B., Kriesell, M.: Antistrong digraphs. J. Combin. Theory Ser. B 122, 68–90 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  3. Chartrand, G., Gavlas, H., Schultz, M., Wall, C.: Anticonnected digraphs. Util. Math. 51, 41–54 (1997)

    MathSciNet  MATH  Google Scholar 

  4. Dobson, E.: Connectivity of circulant digraphs. J. Graph Theory 10, 9–14 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  5. Dobson, E.: On isomorphisms of circulant digraphs of bounded degree. Disc. Math. 308, 6047–6055 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Grünbaum, B.: Antidirected Hamiltonian paths in tournaments. J. Combin. Theory Ser. B 11, 249–257 (1971)

    Article  MathSciNet  MATH  Google Scholar 

  7. Hu, Y., Wei, Y.: Rainbow antistrong connection in tournaments. Graphs Comb. 37, 167–181 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  8. Liang, X., Meng, J., Zhang, Z.: Super-connectivity and hyper-connectivity of vertex transitive bipartite graphs. Graphs Comb. 23, 309–314 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  9. Lu, Z.: On the automorphism groups of bi-cayley graphs. Acta. Sci. Nat. Univ. Pekinensis. 39 (2003)

  10. Meng, J., Huang, Q.: Isomorphisms of circulant diagaphs. Appl. Math. A J. Chin. Univ. 9, 405–409 (1994)

    Article  MATH  Google Scholar 

  11. 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)

  12. Xu, M.: Introduction of Finite Groups II. Science Press, Beijing (1999)

    Google Scholar 

  13. Yuan, L., Meng, J., Sabir, E.: The antistrong property for special digraph families. Graphs Comb. 37, 2511–2519 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  14. Zhang, B., Wu, B.: Anti-Eulerian digraphs. Appl. Math. Comput. 411, 126513 (2021)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Funding

The funding has been received form Natural Science Foundation of Xinjiang Province with Grant nos. 2020D04046, 2021D01C116.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Jixiang Meng.

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.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00373-023-02620-4

Keywords

Navigation