No CrossRef data available.
Article contents
Linkedness and Ordered Cycles in Digraphs
Published online by Cambridge University Press: 01 May 2008
Abstract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.
Given a digraph D, let δ0(D) := min{δ+(D), δ−(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with δ0(D)≥n/2 + l −1 is l-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [17]. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraph D is k-ordered, i.e., that for every sequence s1, . . ., sk of distinct vertices of D there is a directed cycle which encounters s1, . . ., sk in this order. This result will be used in [16].
Information
- Type
- Paper
- Information
- Copyright
- Copyright © Cambridge University Press 2007
References
[1]Bang-Jensen, J. and Gutin, G. (2000) Digraphs: Theory, Algorithms and Applications. Springer.Google Scholar
[2]Bollobás, B. and Thomason, A. (1996) Highly linked graphs. Combinatorica 16 313–320.Google Scholar
[3]Chen, G., Faudree, R. J.Gould, R. J.Jacobson, M. S., Lesniak, L. and Pfender, F. (2004) Linear forests and ordered cycles. Discussiones Mathematicae: Graph Theory 24 359–372.CrossRefGoogle Scholar
[4]Egawa, Y., Faudree, R., Győri, E., Ishigami, Y., Schelp, R. and Wang, H. (2000) Vertex-disjoint cycles containing specified edges. Graphs Combin. 16 81–92.CrossRefGoogle Scholar
[5]Ferrara, M., Gould, R., Tansey, G. and Whalen, T. (2006) On H-linked graphs. Graphs Combin. 22 217–224.CrossRefGoogle Scholar
[6]Fortune, S., Hopcroft, J. E. and Wyllie, J. (1980) The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10 111–121.Google Scholar
[7]Ghouila-Houri, A. (1960) Une condition suffisante d'existence d'un circuit Hamiltonien. CR Acad. Sci. Paris 251 495–497.Google Scholar
[8]Gould, R., Kostochka, A. V. and Yu, G. (2006) On minimum degree implying that a graph is H-linked. SIAM J. Discrete Math. 20 829–840.Google Scholar
[9]Gutin, G. and Yeo, A. (2007) Some parameterized problems on digraphs. Preprint.CrossRefGoogle Scholar
[10]Heydemann, M. C. and Sotteau, D. (1985) About some cyclic properties in digraphs. J. Combin. Theory Ser. B 38 261–278.CrossRefGoogle Scholar
[11]Jung, H. A. (1970) Eine Verallgemeinerung des k-fachen Zusammenhangs für Graphen. Math. Annalen 187 95–103.Google Scholar
[12]Kawarabayashi, K., Kostochka, A. and Yu, G. (2006) On sufficient degree conditions for a graph to be k-linked. Combin. Probab. Comput. 15 685–694.Google Scholar
[13]Kierstead, H., Sarközy, G. and Selkow, S. (1999) On k-ordered Hamiltonian graphs. J. Graph Theory 32 17–25.Google Scholar
[14]Kostochka, A. and Yu, G. (2005) An extremal problem for H-linked graphs. J. Graph Theory 50 321–339.CrossRefGoogle Scholar
[15]Kostochka, A. and Yu, G. Minimum degree conditions for H-linked graphs. Discrete Applied Math., to appear.Google Scholar
[16]Kühn, D., Osthus, D. and Young, A.k-ordered Hamilton cycles in digraphs. Submitted.Google Scholar
[17]Manoussakis, Y. (1990) k-linked and k-cyclic digraphs. J. Combin. Theory Ser. B 48 216–226.Google Scholar
[18]Thomas, R. and Wollan, P. (2005) An improved extremal function for graph linkages. Europ. J. Combin. 26 309–324.Google Scholar
[19]Thomassen, C. (1991) Note on highly connected non-2-linked digraphs. Combinatorica 11 393–395.CrossRefGoogle Scholar
You have
Access
- 9
- Cited by