Erschienen in:

Open Access 11.11.2019

Remarks on Barnette’s conjecture

verfasst von: Jan Florek

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 1/2020

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Patentsuche

Aus

Abstract

Let P be a cubic 3-connected bipartite plane graph having a 2-factor which consists only of facial 4-cycles, and suppose that $P^{*}$ is the dual graph. We show that P has at least $3^{\left\lceil \frac{2|P^{*}|}{\varDelta ^{2}{(P^{*})}}\right\rceil }$ different Hamilton cycles.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Let ${{\mathcal {P}}}$ denote the family of cubic 3-connected bipartite plane graphs. In 1969, Barnette (Tutte 1969, Problem 5) conjectured that every graph in ${{\mathcal {P}}}$ has a Hamilton cycle. In Goodey (1975), Goodey proved that if a graph in ${{\mathcal {P}}}$ has only faces with 4 or 6 sides, then it is hamiltonian (see also Feder and Subi (2006), and Bagheri et al. (2018)). Holton et al. (1985) have used computer search to confirm Barnette’s conjecture for graphs up to 64 vertices. The problem whether a cubic bipartite planar graph has a Hamilton cycle (without the assumption of 3-connectivity) is NP-complete, as shown by Takanori et al. (1980).

All graphs considered in this paper are finite and simple. We use Diestel (2005) as reference for undefined terms. In particular, if P is a plane graph, then V(P) is its vertex set and E(P) is its edge set. The set of neighbours of a vertex v in P is denoted by N(v). |P| is the number of vertices of P and $\varDelta (P)$ is the maximum degree of P. Hence, if $P^{*}$ is the dual graph of P, then $|P^{*}|$ is the number of faces in P, and $\varDelta (P^{*})$ is the maximum size of faces in P.

Let ${{\mathcal {P}}}(4)$ be the family of all graphs in ${{\mathcal {P}}}$ which possess a 2-factor consisting only of facial 4-cycles. The following theorem yields a lower bound on the number of Hamilton cycles in every graph belonging to ${{\mathcal {P}}}(4)$.

Theorem 1

Every graph $P \in {{\mathcal {P}}}(4)$ has at least $3^{\left\lceil \frac{2|P^{*}|}{\varDelta ^{2}{(P^{*})}}\right\rceil }$ different Hamilton cycles.

A sequence of faces in a plane graph P is a sequence of different faces in P such that two faces from the sequence are adjacent if and only if they are consecutive in the sequence. A sequence of faces $f_{0}f_{1} \ldots f_{k}$ in P is called a sequence from $f_0$ to $f_k$ of lengthk. The distance of two faces f, h in P is the length of the shortest sequence of faces from f to h. We prove the following theorem which generalizes some results obtained by Florek in Florek (2010).

Theorem 2

Let $P\in {{\mathcal {P}}}(4)$ and suppose that M is a set of faces in P such that the distance of any two different faces in M is greater than 4. If for every face in M any its edge is chosen, then there is a Hamiltonian cycle in P containing all the remaining edges of faces in M.

We will use a result that expresses hamiltonicity in terms of the dual graph. Let ${{\mathcal {E}}}$ be the dual family to ${{\mathcal {P}}}$, i.e., ${{\mathcal {E}}}$ is the family of all Eulerian plane triangulations. Let $G \in {{\mathcal {E}}}$. Stein (1971) proved that $G^{*}$ is hamiltonian if and only if G possesses two disjoint induced acyclic subgraphs which together contain all vertices of G (see also Florek 2016) .

Let ${{\mathcal {E}}}(4)$ be the dual family to ${{\mathcal {P}}}(4)$. Our aim is to prove the following two theorems which express the theorems formulated above in the dual form:

Theorem 3

Every graph $G \in {{\mathcal {E}}}(4)$ has at least $3^{\left\lceil \frac{2|G|}{\varDelta ^{2}(G)}\right\rceil }$ different pairs of disjoint induced acyclic subgraphs which together contain all vertices of G.

Theorem 4

Let $G \in {{\mathcal {E}}}(4)$ and suppose that $L \subset V(G)$ is a set of vertices such that the distance of every two different vertices of L is greater than 4. If for every $v \in L$ any vertex $n(v) \in N(v)$ is chosen, then there are two induced acyclic subgraphs which together contain all vertices of G and one of them contains the set $N(v) \backslash \{n(v)\}$, for every $v \in L$.

In the proof of Theorem 3 we will us the following greedy algorithm (see Diestel 2005): starting from a fixed vertex enumeration $v_{1}, \ldots , v_{m}$ of G, we consider the vertices in turn and colour each $v_{i}$ with the first available colour—e.g., with the smallest positive integer not already used to colour any neighbour of $v_{i}$ among $v_{1}, \ldots , v_{i-1}$. In this way, we never use more than $\varDelta (G) +1$ colours, even for unfavourable choices of the enumeration $v_{1}, \ldots , v_{m}$. Notice that greedy algorithm gives a constructive method to find an independent set in G which has at least $\frac{|G|}{\chi (G)} \geqslant \frac{|G|}{\varDelta (G)+1}$ vertices.

2 Proofs

Let $G\in {{\mathcal {E}}}(4)$. It is well known that every Eulerian plane triangulation has a proper 3-colouring of vertices. Let $\{B, W, R\}$ be the corresponding vertex partition of V(G) into independent black, white and red colour classes. Certainly, one of them (say R) contains only vertices of degree 4. In Figs. 1, 2, 3 the vertices of B, W and R are indicated by black circles, white circles and squares, respectively.

Florek (2010) proved that every graph in ${{\mathcal {E}}}(4)$ is 4-connected. Hence, the set of neighbours of any vertex in G induces a cycle of G. For a path svt, which is disjoint with R, we define an operation$\alpha = \alpha (s,v,t)$ in the following way: let $v_{1} \ldots v_{n} v_{1}$ be a cycle induced by neighbours of v ($s = v_1$ and $t = v_k$). Replace the vertex v with a path xuy and join the vertices of this path with the former neighbours of v in such a way that x is adjacent to $v_{1}, \ldots , v_{k}$, u is adjacent to $v_1$ and $v _k$, and y is adjacent to $v_{k}, \ldots , v_{n}, v_{1}$. Let $\alpha (G)$ be the graph constructed from G by $\alpha $. We put $\alpha (R) = R\cup \{u\}$, $\alpha (B) = B$ and $\alpha (W) = (W\backslash \{v\})\cup \{x, y\}$, for $v \in W$ (similarly, $\alpha (B) = (B\backslash \{v\})\cup \{x, y\}$ and $\alpha (W) = W$, for $v \in B$, respectively). Notice that $\alpha (G) \in {{\mathcal {E}}}(4)$, because $\{\alpha (B), \alpha (W), \alpha (R)\}$ is a vertex partition of $V(\alpha (G))$ into independent colour classes such that $\alpha (R)$ contains only vertices of degree 4. It was proved in Florek (2010) that every graph $G\in {{\mathcal {E}}}(4)$ can be constructed (up to isomorphism) from the octahedron by iterating the operation $\alpha $. Hence, by induction we obtain:

(i) $|B \cup W| = \frac{|G|}{2} +1$.

Definition 1

We say that a pair (C, D) of disjoint induced subgraphs of G is (black,white)-closed if the following two conditions are satisfied (see Figs. 1 and 3):

(1)

if $v \in B$ ($v \in B\backslash V(D)$) is adjacent with a white (red, respectively) vertex of C, then v is a vertex of C,

(2)

if $v \in W$ ($v \in W\backslash V(C)$) is adjacent with a black (red, respectively) vertex of D, then v is a vertex of D.

Lemma 1

Let $G \in {{\mathcal {E}}}(4)$ and suppose that V(G) has a vertex partition into independent red, black and white colour classes such that the red colour class contains only vertices of degree 4. Every pair of disjoint (black, white)-closed induced acyclic subgraphs of G can be extended to such a pair of disjoint induced acyclic subgraphs which together contain all vertices of G.

Proof

Let (C, D) be a pair of disjoint (black,white)-closed induced acyclic subgraphs of G. First we add to C (or D) all black (white, respectively) vertices which not belong to $C\cup D$. Then we obtain a pair $(C', D')$ of disjoint induced acyclic subgraphs of G. Next we consider any red vertex v not belonging to $C \cup D$. Since $(C', D')$ is (black,white)-closed and all neighbours of v belong to $C' \cup D'$ one of the following cases occurs:

(j)

two black neighbours of v belong to $C'$,

(jj)

two white neighbours of v belong to $D'$.

If black neighbours of v belong to a path contained in $C'$, then we add v to $D'$. If white neighbours of v belong to a path contained in $D'$ then we add v to $C'$. Otherwise, we add v to $C'$ or $D'$. Then we obtain a pair (X, Y) of disjoint induced acyclic subgraphs of G such that $C' \subset X$, $D' \subset Y$ and $V(X) \cup V(Y) = V(G)$ (see Figs. 1 and 2). $\square $

Now we are ready to prove Theorems 3 and 4.

Proof of Theorem 3

Proof

Suppose that $G[B\cup W]$ is a subgraph of G induced by all black and white vertices of G. For every different vertices a, b of $G[B\cup W]$ which have the same colour and $d_{G}(a,b) = 2$ we add the edge ab to $G[B\cup W]$. Then we obtain a graph J such that

$$\begin{aligned} \varDelta (J) \leqslant \frac{\varDelta (G)}{2} + \frac{\varDelta (G)}{2} (\frac{\varDelta (G)}{2}-1) - 1 < \frac{\varDelta ^{2}(G)}{4}. \end{aligned}$$

Thus, by the greedy algorithm, $\chi (J) \leqslant \frac{\varDelta ^{2}(G)}{4}$. Hence, J has an independent set of vertices K which, by (i), has at least

$$\begin{aligned} |K| \geqslant \frac{|J|}{\chi (J)} = \frac{|B\cup W|}{\chi (J)} > \frac{2|G|}{\varDelta ^{2}(G)} \end{aligned}$$

vertices.

Notice that $K \subset V(J) = B \cup W \subset V(G)$. Suppose that for every $v \in K$ any red vertex $n(v) \in N(v)$ is chosen. Since G is 4-connected, $N(v) \backslash \{n(v)\}$ induces a path-subgraph in G which is denoted as P(v, n(v)). If v is black (white), then $(N(v) \cap W) \cup \{v\}$ ($(N(v) \cap B)\cup \{v\}$, respectively) induces a star-subgraph in G, denoted as S(v).

Suppose that $W_{1} \subset {K \cap W}$ and $B_{1} \subset {K \cap B}$ is chosen. Let $W_{2} ={ K \cap W} \backslash W_{1}$ and suppose that $B_{2} = {K \cap B}\backslash B_{1}$. Notice that

$$\begin{aligned} C = \bigcup _{v \in W_1} P(v, n(v)) \cup \bigcup _{v \in W_2} S(v) \hbox { and } D = \bigcup _{v \in B_1} P(v, n(v)) \cup \bigcup _{v \in B_2} S(v) \end{aligned}$$

are disjoint induced acyclic subgraphs of G because $d_{G}(a,b)\geqslant 4$ ($\geqslant 3$), for every different vertices $a, b \in K$ of the same colour class (of different colour classes, respectively). Remark that every black (white) vertex, which is adjacent with a vertex belonging to C (or D) belongs to C (D, respectively). Thus, (C, D) is (black,white)-closed (see Fig. 3). Hence follows that G has at least

$$\begin{aligned} \prod _{v \in K} \left( \frac{deg_{G}(v)}{2} + 1\right) \geqslant 3^{|K|} \geqslant 3^{\left\lceil \frac{2|G|}{\varDelta ^{2}(G)}\right\rceil } \end{aligned}$$

different pairs of disjoint (black,white)-closed induced acyclic subgraphs. Thus, by Lemma 1, G has at least $3^{\left\lceil \frac{2|G|}{\varDelta ^{2}(G)}\right\rceil }$ different pairs of disjoint induced acyclic subgraphs which together contain all vertices of G. $\square $

Proof of Theorem 4

Proof

Let $L \subset V(G)$ be a set of vertices such that $d(a,b) \geqslant 5$ for every different vertices $a, b \in L$.

Suppose that for every $v \in V(G)$ any vertex $n(v) \in N(v)$ is chosen. Since G is 4-connected, $N(v) \backslash \{n(v)\}$ induces a path-subgraph in G which is denoted as P(v, n(v)). Let $R_b$ (or $R_w$) be the set of all $v \in R$ such that n(v) is black (white, respectively). If $v \in W \cup R_b$ ($v \in B \cup R_w$), then $(N(n(v)) \cap W) \cup \{n(v)\}$ ($(N(n(v)) \cap B)\cup \{n(v)\}$, respectively) induces a star-subgraph in G, denoted as S(n(v)). Notice that if v is white (black), then the pair (P(v, n(v)), S(n(v)) ((S(n(v)), P(v, n(v))), respectively) is (black,white)-closed (see Fig. 1). Hence,

$$\begin{aligned} (\bigcup _{v \in W \cap L} P(v,n(v)) \cup \bigcup _{v \in (B \cup R_w) \cap L} S(n(v)), \bigcup _{v \in B \cap L} P(v,n(v)) \cup \bigcup _{v \in (W \cup R_b)\cap L} S(n(v)) \end{aligned}$$

is a pair of disjoint (black,white)-closed induced acyclic subgraphs of G, because $d(a,b)\geqslant 5$, for every different $a, b \in L$.

Hence, by Lemma 1, G has a pair (X, Y) of disjoint induced acyclic subgraphs which together contain all vertices of G and such that ${P(v,n(v)) \subset X}$, for $v \in W\cap L$, $S(n(v))\subset X$, for $v \in R_w\cap L$, $P(v,n(v)) \subset Y$, for $v \in B\cap L$ and $S(n(v))\subset Y$, for $v \in R_b\cap L$. $\square $

Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Vorheriger Artikel Approximation algorithm for a generalized Roman domination problem in unit ball graphs

Nächster Artikel Tree-coloring problems of bounded treewidth graphs

Springer Professional

Abstract

Publisher's Note

1 Introduction

2 Proofs

Publisher's Note

Weitere Artikel der Ausgabe 1/2020

Dynamic three-stage operating room scheduling considering patient waiting time and surgical overtime costs

Approximation algorithm for a generalized Roman domination problem in unit ball graphs

Graphs with equal domination and covering numbers

On the König deficiency of zero-reducible graphs

Algorithmic results on double Roman domination in graphs

Efficient algorithms for measuring the funnel-likeness of DAGs