Hostname: page-component-8448b6f56d-c47g7 Total loading time: 0 Render date: 2024-04-18T02:25:42.869Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 22 , Issue 5 , September 2013 , pp. 684 - 699
Copyright
Copyright © Cambridge University Press 2013 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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