Spanning connectedness and Hamiltonian thickness of graphs and interval graphs
Peng Li, Yaokun Wu
Abstract
A spanning connectedness property is one which involves the robust
existence of a spanning subgraph which is of some special form, say a
Hamiltonian cycle in which a sequence of vertices appear in an
arbitrarily given ordering, or a Hamiltonian path in the subgraph
obtained by deleting any three vertices, or three
internally-vertex-disjoint paths with any given endpoints such that
the three paths meet every vertex of the graph and cover the edges of
an almost arbitrarily given linear forest of a certain fixed size.
Let π=π1⋯πn be an
ordering of the vertices of an n-vertex graph
G. For any positive integer k≤n-1, we
call π a k-thick Hamiltonian vertex
ordering of G provided it holds for all
i∈{1, …, n-1} that
πiπi+1∈E(G) and the
number of neighbors of πi among
{πi+1, …,
πn} is at least min(n-i,
k); For any nonnegative integer k, we say
that π is a -k-thick Hamiltonian vertex
ordering of G provided
|{i: πiπi+1∉E(G),
1≤i≤n-1}|≤k+1. Our main discovery
is that the existence of a thick Hamiltonian vertex ordering will
guarantee that the graph has various kinds of spanning connectedness
properties and that for interval graphs, quite a few seemingly
unrelated spanning connectedness properties are equivalent to the
existence of a thick Hamiltonian vertex ordering. Due to the
connection between Hamiltonian thickness and spanning connectedness
properties, we can present several linear time algorithms for
associated problems. This paper suggests that much work in graph
theory may have a spanning version which deserves further study, and
that the Hamiltonian thickness may be a useful concept in
understanding many spanning connectedness properties.
Full Text: PDF