Hostname: page-component-74656f9884-6grmk Total loading time: 0 Render date: 2026-11-06T07:57:43.360Z Has data issue: false hasContentIssue false
  • English
  • Français

Degree Conditions for H-Linked Digraphs

Published online by Cambridge University Press:  08 August 2013

MICHAEL FERRARA ,
MICHAEL JACOBSON  and
FLORIAN PFENDER
MICHAEL FERRARA
Affiliation:
Department of Mathematical and Statistical Sciences, University of Colorado Denver, Denver, CO 80217, USA (e-mail: michael.ferrara@ucdenver.edu, michael.jacobson@ucdenver.edu, florian.pfender@ucdenver.edu)
MICHAEL JACOBSON
Affiliation:
Department of Mathematical and Statistical Sciences, University of Colorado Denver, Denver, CO 80217, USA (e-mail: michael.ferrara@ucdenver.edu, michael.jacobson@ucdenver.edu, florian.pfender@ucdenver.edu)
FLORIAN PFENDER
Affiliation:
Department of Mathematical and Statistical Sciences, University of Colorado Denver, Denver, CO 80217, USA (e-mail: michael.ferrara@ucdenver.edu, michael.jacobson@ucdenver.edu, florian.pfender@ucdenver.edu)
Rights & Permissions [Opens in a new window]

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 (multi)digraph H, a digraph D is H-linked if every injective function ι:V(H) → V(D) can be extended to an H-subdivision. In this paper, we give sharp degree conditions that ensure a sufficiently large digraph D is H-linked for arbitrary H. The notion of an H-linked digraph extends the classes of m-linked, m-ordered and strongly m-connected digraphs.

First, we give sharp minimum semi-degree conditions for H-linkedness, extending results of Kühn and Osthus on m-linked and m-ordered digraphs. It is known that the minimum degree threshold for an undirected graph to be H-linked depends on a partition of the (undirected) graph H into three parts. Here, we show that the corresponding semi-degree threshold for H-linked digraphs depends on a partition of H into as many as nine parts.

We also determine sharp Ore–Woodall-type degree-sum conditions ensuring that a digraph D is H-linked for general H. As a corollary, we obtain (previously undetermined) sharp degree-sum conditions for m-linked and m-ordered digraphs.

Keywords

Primary 05C2005C38Secondary 05C40

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 5 , September 2013 , pp. 684 - 699
Copyright
Copyright © Cambridge University Press 2013 

References

[1]Diestel, R. (2005) Graph Theory, Springer.Google Scholar
[2]Ferrara, M., Gould, R., Jacobson, M., Pfender, F., Powell, J. and Whalen, T. (2012) New Ore-type degree conditions for H-linked graphs. J. Graph Theory 71 69–77.Google Scholar
[3]Ferrara, M., Gould, R., Tansey, G. and Whalen, T. (2006) On H-linked graphs. Graphs. Combin. 22 217–224.Google Scholar
[4]Ferrara, M., Gould, R., Tansey, G. and Whalen, T. (2008) On H-immersions. J. Graph Theory 57 245–254.Google Scholar
[5]Gould, R., Kostochka, A. and Yu, G. (2006) On minimum degree implying that a graph is H-linked. SIAM J. Discrete Math. 20 829–840.CrossRefGoogle Scholar
[6]Karawabayashi, 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
[7]Kierstead, H., Sarközy, G. and Selkow, S. (1999) On k-ordered Hamiltonian graphs. J. Graph Theory 32 17–25.Google Scholar
[8]Kostochka, A. and Yu, G. (2008) Minimum degree conditions for H-linked graphs. Discrete Appl. Math. 156 1542–1548.Google Scholar
[9]Kühn, D. and Osthus, D. (2008) Linkedness and ordered cycles in digraphs. Combin. Probab. Comput. 17 689–709.Google Scholar
[10]Manoussakis, Y. (1990) k-linked and k-cyclic digraphs. J. Combin. Theory Ser. B 48 216–226.Google Scholar
[11]Thomassen, C. (1991) Highly connected non-2-linked digraphs. Combinatorica 11 393–395.CrossRefGoogle Scholar
[12]Woodall, D. (1972) Sufficient conditions for circuits in graphs. Proc. London Math. Soc. 24 739–755.Google Scholar