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

Every Cycle-Connected Multipartite Tournament with δ ≥ 2 Contains At Least Two Universal Arcs

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

Abstract

A digraph D = (V(D), A(D)) is called cycle-connected if for every pair of vertices \({u, v\in V(D)}\) there exists a cycle containing both u and v. Ádám (Acta Cybernet 14(1):1–12, 1999) proposed the question: Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc \({e\in A(D)}\) such that for every vertex \({w\in V(D)}\) there exists a cycle C in D containing both e and w?. Recently, Lutz Volkmann and Stefan Winzen have proved that this conjecture is true for multipartite tournaments. As an improvement of this result, we show in this note that every cycle-connected multipartite tournament with δ ≥ 2 contains at least two universal arcs.

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

Similar content being viewed by others

References

  1. Ádám A.: On some cyclic connectivity properties of directed graphs. Acta Cybernet. 14(1), 1–12 (1999)

    MathSciNet  MATH  Google Scholar 

  2. Bang-Jensen J., Gutin G.: Digraphs: Theory Algorithms and Applications. Springer, Berlin (2001)

    Google Scholar 

  3. Guo Y., Pinkernell A., Volkmann L.: On cycles through a given vertex in multipartite tournaments. Discrete Math. 164, 165–170 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  4. Hetyei G.: Cyclic connectivity classes of directed graphs, Acta Math. Acad. Paedagog. Nyházi 17(2), 47–59 (2001)

    MathSciNet  MATH  Google Scholar 

  5. Hubenko A.: On a cyclic connectivity property of directed graphs. Discrete Math. 308, 1018–1024 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  6. Moon J.W.: On subtournaments of a tournament. Can. Math. Bull. 9, 297–301 (1966)

    Article  MATH  Google Scholar 

  7. Volkmann L.: Cycles in multipartite tournaments: results and problems. Discrete Math. 245, 19–53 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Volkmann L., Winzen S.: Every cycle-connected multipartite tournament has a universal arc. Discrete Math. 309, 1013–1017 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Xidian University, Xi’an, 710071, People’s Republic of China

    Qingsong Zou

  2. School of Mathematics, Shandong University, Jinan, 250100, People’s Republic of China

    Guojun Li

  3. School of Mathematics and Computer Science, Ningxia University, Yinchuan, 750021, People’s Republic of China

    Yunshu Gao

Authors
  1. Qingsong Zou
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Guojun Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yunshu Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Qingsong Zou.

Additional information

This work is supported by the National Natural Science Foundation of China (Grant No. 61070095, 11161035) and Ningxia Ziran (Grant No. NZ1153).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zou, Q., Li, G. & Gao, Y. Every Cycle-Connected Multipartite Tournament with δ ≥ 2 Contains At Least Two Universal Arcs. Graphs and Combinatorics 29, 1141–1149 (2013). https://doi.org/10.1007/s00373-012-1170-2

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-012-1170-2

Keywords

Mathematics Subject Classification

Search

Navigation