Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The Antistrong Property for Special Digraph Families

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

Abstract

A walk with no arc repeated which begins and ends with forward arcs, in which the arcs alternate between forward and backward arcs, is called forward antidirected trail. A digraph D with order at least three containing a forward antidirected (x, y)-trail for every pair of distinct vertices x, y of D is antistrong. In this paper, we show that the Cartesian product of two antistrong digraphs is antistrong. Moreover, one of the results is that the Lexicographic product of an antistrong digraph and a digraph is antistrong. Finally, the subject is researched to give a necessary and sufficient condition to decide whether a tournament is antistrong.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2 
Fig. 3

Similar content being viewed by others

References

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

    Book  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. Klavžar, S.: Coloring graph products–a survey. Discrete Math. 155, 135–145 (1996)

    Article  MathSciNet  Google Scholar 

  6. Stadler, B.M.R., Stadler, P.F.: The topology of evolutionary biology. In: Modelling in Molecular Biology, Springer, pp. 267–286 (2004)

  7. Wagner, G., Stadler, P.F.: Quasi-independence, homology and the unity of type: a topological theory of characters. J. Theoret. Biol. 220, 505–527 (2003)

    Article  MathSciNet  Google Scholar 

  8. Archambault, D., Munzner, T., Auber, D.: TopoLayout: multilevel graph layout by topological features. IEEE Trans. Vis. Comput. Graph. 13(2), 305–317 (2007)

    Article  Google Scholar 

  9. Jänicke, S., Heine, C., Hellmuth, M., Stadler, P., Scheuermann, G.: Visualization of graph products. IEEE Trans. Vis. Comput. Graph. 16(6), 1082–1089 (2010)

    Article  Google Scholar 

  10. Kaveh, A.: Optimal Analysis of Structures by Concepts of Symmetry and Regularity. Springer, Berlin (2013)

    Book  Google Scholar 

  11. Kaveh, A., Koohestani, K.: Graph products for configuration processing of space structures. Comput. Struct. 86(11–12), 1219–1231 (2008)

    Article  Google Scholar 

  12. Kaveh, A., Rahami, H.: An efficient method for decomposition of regular structures using graph products. Internat J. Numer. Methods Eng. 61(11), 1797–1808 (2004)

    Article  MathSciNet  Google Scholar 

  13. Hammack, R., Imrich, W., Klavžar, S.: Handbook of Product Graphs, 2nd edn. CRC Press, Boca Roton (2011)

    Book  Google Scholar 

  14. Imrich, W., Klavžar, S.: Product Graphs. Wiley-Intersci. Ser. Discrete Math. Optim. Wiley-Interscience, New York (2000)

    MATH  Google Scholar 

  15. Chiue, W.S., Shieh, B.S.: On connectivity of the cartesian product of two graphs. Appl. Math. Comput. 102, 129–137 (1999)

    MathSciNet  MATH  Google Scholar 

  16. Špacapan, S.: Connectivity of Cartesian products of graphs. Appl. Math. Lett. 21, 682–685 (2008)

    Article  MathSciNet  Google Scholar 

  17. Györi, E., Plummer, M.: The cartesian product of a \(k\)-extendable and an \(l\)-extendable graph is \((k + l + 1)\)-extendable. Discrete Math. 101, 87–96 (1992)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

The authors would like to express their gratitude to the editor and anonymous reviewers for their valuable comments and constructive suggestions on the original manuscript. This research is supported by the Natural Science Foundation of Xinjiang Province, China (Nos. 2020D04046, 2021D01C116).

Author information

Authors and Affiliations

  1. College of Mathematics and System Science, Xinjiang University, 830046, Urumqi, China

    Lili Yuan, Jixiang Meng & Eminjan Sabir

Authors
  1. Lili Yuan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jixiang Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eminjan Sabir
    View author publications

    You can also search for this author in PubMed Google Scholar

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 (No. 2020D04046, 2021D01C116)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yuan, L., Meng, J. & Sabir, E. The Antistrong Property for Special Digraph Families. Graphs and Combinatorics 37, 2511–2519 (2021). https://doi.org/10.1007/s00373-021-02375-w

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-021-02375-w

Keywords

Search

Navigation