A graph
is
𝒫, abbreviated
𝒫, if for every vertex
in
the open neighbourhood
) of
is non-empty and induces a graph with property 𝒫. Specifically, a graph
without isolated vertices is
(
) if
) ...induces a connected graph for each
∈
(
), and
(
) if
) induces a hamiltonian graph for each
∈
(
). A graph
is
𝒫 (abbreviated
𝒫) if
) is non-empty and induces a locally 𝒫 graph for every
∈
(
). This concept is generalized to an arbitrary degree of nesting. For any
0 we call a graph
if it is
for
= 0, 1, . . .,
and
(with
and
meaning
and
, respectively). The class of locally
-nested-hamiltonian graphs contains important subclasses. For example, Skupień had already observed in 1963 that the class of connected
graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any
≥ 1 the class of locally
-nested-hamiltonian graphs contains all simple-clique (
+ 2)-trees. In 1979 Oberly and Sumner proved that every connected
-free graph that is locally connected is hamiltonian. They conjectured that for
≥ 1, every connected
-free graph that is locally (
+ 1)-connected is hamiltonian. We show that locally
-nested-hamiltonian graphs are locally (
+ 1)-connected and consider the weaker conjecture that every
-free graph that is locally
-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be “best possible” in the sense that for every
≥ 1 there exist
-free locally
-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally
-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally
-nested-hamiltonian graphs with restricted maximum degree.
The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition ...(V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.
The Existence of Planar Hypotraceable Oriented Graphs van Aardt, Susan; Burger, Alewyn Petrus; Frick, Marietjie
Discrete mathematics and theoretical computer science,
01/2017, Volume:
19, Issue:
1
Journal Article
Peer reviewed
Open access
A digraph is \emph{traceable} if it has a path that visits every vertex. A digraph DD is \emph{hypotraceable} if DD is not traceable but D−vD−v is traceable for every vertex v∈V(D)v∈V(D). It is known ...that there exists a planar hypotraceable digraph of order nn for every n≥7n≥7, but no examples of planar hypotraceable oriented graphs (digraphs without 2-cycles) have yet appeared in the literature. We show that there exists a planar hypotraceable oriented graph of order nn for every even n≥10n≥10, with the possible exception of n=14n=14.
In 1982 Laborde, Payan and Xuong Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982) 173-177 (Teubner-Texte Math., 59 1983) conjectured ...that every digraph has an independent detour transversal (IDT), i.e. an independent set which intersects every longest path. Havet Stable set meeting every longest path, Discrete Math. 289 (2004) 169-173 showed that the conjecture holds for digraphs with independence number two. A digraph is p-deficient if its order is exactly p more than the order of its longest paths. It follows easily from Havet’s result that for p = 1, 2 every p-deficient digraph has an independent detour transversal. This paper explores the existence of independent detour transversals in 3-deficient digraphs.
Graphs and Algorithms
A digraph is k-traceable if each of its induced subdigraphs of order k is traceable. The Traceability Conjecture is that for k ≥ 2 every k-traceable oriented graph of order at ...least 2k − 1 is traceable. The conjecture has been proved for k ≤ 5. We prove that it also holds for k = 6.
We say a graph G is locally P if for each vertex v in G the open neighbourhood of v induces a graph with property P. The Hamilton Cycle Problem (HCP) is the problem of deciding whether a graph ...contains a Hamilton cycle. It is known that the HCP is NP-complete for locally traceable (LT) graphs with maximum degree 6. We extend that result to 1-tough graphs and to graphs with restricted degree sequences. If R is a set of nonnegative integers, we say a graph G is R-regular if the degrees of all the vertices in V(G) are elements of R. We show that the HCP is NP-complete for R-regular LT graphs if R is any set of natural numbers with max(R)≥6, with the possible exception of {4,6} and {6}. It is known that the HCP is NP-complete for LH graphs with maximum degree 10. We improve this result by showing that the HCP is NP-complete for 1-tough LH graphs with maximum degree 9 and for R-regular LH graphs if R is any set of natural numbers with min(R)=3 and max(R)∈{9,10}, or if R is any set of natural numbers with max(R)≥11. Finally, we show that the HCP for k-connected LH graphs that are also locally (k−1)-connected is NP-complete for every k≥3.
Proper connection and size of graphs van Aardt, Susan A.; Brause, Christoph; Burger, Alewyn P. ...
Discrete mathematics,
November 2017, 2017-11-00, Volume:
340, Issue:
11
Journal Article
Peer reviewed
Open access
An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph G, denoted by ...pc(G), is the smallest number of colours that are needed in order to make G properly connected. Our main result is the following: Let G be a connected graph of order n and k≥2. If |E(G)|≥n−k−12+k+2, then pc(G)≤k except when k=2 and G∈{G1,G2}, where G1=K1∨(2K1+K2) and G2=K1∨(K1+2K2).
The Path Partition Conjecture (PPC) states that if G is any graph and (λ1, λ2) any pair of positive integers such that G has no path with more than λ1 + λ2 vertices, then there exists a partition ...(V1, V2) of the vertex set of G such that Vi has no path with more than λi vertices, i = 1, 2. We present a brief history of the PPC, discuss its relation to other conjectures and survey results on the PPC that have appeared in the literature since its first formulation in 1981.
If P is a given graph property, we say that a graph G is locallyP if 〈N(v)〉 has property P for every v∈V(G) where 〈N(v)〉 is the induced graph on the open neighbourhood of the vertex v. We consider ...the complexity of the Hamilton Cycle Problem for locally traceable and locally hamiltonian graphs with small maximum degree. The problem is fully solved for locally traceable graphs with maximum degree 5 and also for locally hamiltonian graphs with maximum degree 6 (van Aardt et al., 2016). We show that the Hamilton Cycle Problem is NP-complete for locally traceable graphs with maximum degree 6 and for locally hamiltonian graphs with maximum degree 10. We also show that there exist regular connected nonhamiltonian locally hamiltonian graphs with connectivity 3, thus answering two questions posed by Pareek and Skupień (1983).
PDF
