Vertex pancyclicity over lexicographic products

Abstract

A lexicographic product of graphs G and H, denoted by $G°H,$ is defined as a graph with the vertex set $V(G)\times V(H)$ and an edge $\{(u_1,v_1),(u_2,v_2)\}$ presents in the product whenever $u_1{u}_2\in E(G)$ or (u₁ = u₂ and $v_1{v}_2\in E(H)$). We investigate the sufficient conditions for vertex pancyclicity of lexicographic products of complete graphs K_n, paths P_n or cycles C_n with a general graph. We obtain that (i) if G₁ is a traceable graph of even order and G₂ is a graph with at least one edge, then $G_1°G_2$ is vertex pancyclic; (ii) if G₁ is hamiltonian and G₂ is a graph with at least one edge, then $G_1°G_2$ is vertex pancyclic.

Keywords:

• Traceble
• hamiltonian
• vertex pancyclic
• lexicographic product

MATHEMATICAL SUBJECT CLASSIFICATION:

• 05C38
• 05C45

1. Introduction

We consider a finite, undirected, simple graph G with the vertex set V(G) and the edge set E(G). The maximum degree of G is denoted by $\Delta (G).$ Most of the basic graph theory terminologies in this work follow from West’s textbook [11]. An (s, t)-path of G is a path in G from vertex s to vertex t, denoted by P(s, t). Then, P(t, s) denotes the reversed path of P(s, t). The length of a path or cycle is the number of its edges. A path in G is a hamiltonian path or a spanning path if it contains all the vertices of G. A graph G is traceable if G contains a hamiltonian path. A cycle of G is a hamiltonian cycle if it contains all the vertices of G. A graph G is said to be hamiltonian if it contains a hamiltonian cycle. Otherwise, G is non-hamiltonian. A graph G of order n is said to be pancyclic if it contains a cycle of each length l for $3\le l\le n.$ A vertex of G is a k-vertex pancyclic if it is contained in a cycle of each length l for $k\le l\le n,$ and a graph G is a vertex k-pancyclic if all vertices of G are k-vertex pancyclic. We usually use pancyclic and vertex pancyclic instead of 3-vertex pancyclic and vertex 3-pancyclic, respectively. A graph G is said to be vertex even pancyclic if each vertex of G is contained in a cycle of each even length l for $3<l\le n.$

In 1971, Bondy [2] posed the metaconjecture which stated that almost any nontrivial sufficient condition on a graph which implies that the graph is hamiltonian also implies that the graph is pancyclic, otherwise there may be a simple family of exceptional graphs. There are several works supporting this metaconjecture (see [10]). Apart from pancyclicity, there are a number of works show that those conditions also imply that the graph is vertex pancyclic. For instance, in 1960, Ore [8] introduced degree sum condition which was stated that “for each pair of non-adjacent vertices u, v in G, $d(u)+d(v)\ge n(G)$”and showed that if G is a graph satisfying the degree sum condition, then G is hamiltonian. Bondy [3] showed that if G is graph satisfying the degree sum condition, then G is pancyclic or $G=K_{n/2,n/2}.$ In 1984, Xiaotao Cai [5] considered the degree sum condition and proved that a graph G satisfying this condition is vertex 4-pancyclic or $G=K_{n/2,n/2}$ (see [10] for more examples).

Let G and H be two graphs. The cartesian product of graphs G and H, denoted by $G\square H,$ is defined as a graph with the vertex set $V(G)\times V(H)$ and an edge $\{(u_1,v_1),(u_2,v_2)\}$ presents in the cartesian product whenever u₁ = u₂ and $v_1{v}_2\in E(H)$ or symmetrically v₁ = v₂ and $u_1{u}_2\in E(G).$

The lexicographic product or graph composition of graphs G and H, denoted by $G°H,$ is defined as a graph with the vertex set $V(G)\times V(H)$ and an edge $\{(u_1,v_1),(u_2,v_2)\}$ presents in the lexicographic product whenever $u_1{u}_2\in E(G)$ or (u₁ = u₂ and $v_1{v}_2\in E(H)$). The double graph of a graph G is $G°P_2.$

From the definitions of the cartesian product and the lexicographic product of graphs G and H, we can see that $V(G\square H)=V(G°H)$ and $E(G\square H)\subset E(G°H).$ Therefore, the vertex pancyclicity over $G\square H$ implies the vertex pancyclicity over $G°H.$ Here, we only consider vertex pancyclicity over $G°H$ on the conditions that do not imply vertex pancyclic over $G\square H.$

For cartesian products, they also have a bunch of works relating to the metaconjecture, i.e., almost any nontrivial condition on a cartesian product which implies that the cartesian product is hamiltonian also implies that the cartesian product is pancyclic (there may be a simple family of exceptional graphs).

Theorem 1.

[9] If G is a 3-connected cubic graph, then $G\square P_2$ is hamiltonian.

Theorem 2.

[9] If G is an even 3-cactus, then $G\square P_2$ is hamiltonian.

A cactus is a connected graph in which every block is a K₂ or a cycle, where a block is a maximal 2-connected subgraph. A 3-cactus is a cactus with maximum degree 3. An even 3-cactus is a 3-cuctus in which all of its cycles are of even length.

Theorem 3.

[1] If G is a connected graph, then $G\square K_n$ is hamiltonian for $\Delta (G)\le n.$

Theorem 4.

[4] If G is a connected graph, then $G\square C_n$ is hamiltonian for $\Delta (G)\le n.$

Theorem 5.

[4] Let G be a connected almost claw-free graph and $n\ge 4$ be an even integer. Then, $G\square P_n$ is hamiltonian.

However, such conditions only imply that a cartesian product is vertex even pancyclic as follows.

Theorem 6.

[6] If G is a 3-connected cubic graph, then $G\square P_2$ is vertex even pancyclic.

Theorem 7.

[6] If G is an even 3-cactus, then $G\square P_2$ is vertex even pancyclic.

Theorem 8.

[4] Let n be even and $n\ge 4$. If G is a 1-pendent cactus with $\Delta (G)\le \frac{1}{2}(n+2)$, then $G\square P_n$ is vertex even pancyclic.

A claw is a $K_{1,3}.$ The vertex of degree 3 is its center. For a set $B\subseteq V(G),$ B is a dominating set if every vertex of G is in B or has a neighbor in B. A graph G is 2-dominated if the size of a minimum dominating set of G is at most 2. A graph G is called an almost claw-free graph if the set of center vertices of induced claws in G is independent and the neighborhood of each center vertex induces a 2-dominated subgraph. For a graph G, a vertex of degree 1 in G is called pendent if its neighbor is a vertex of degree at least 3 in G. A 1-pendent cactus is a cactus in which every vertex v has at most 1 pendent neighbor (v can have other non pendent neighbors).

Here, we notice that vertex pancyclicity over cartesian products is affected by the number of edges between each copy of a graph. This motivates us to consider lexicographic product that contains more edges.

For the pancyclicity of lexicographic products, there are a few results. In 2006, Kaiser and Kriesell [7] investigated toughness conditions on a graph G that the lexicographic product of G and a graph is hamiltonian and also pancyclic in which stated that if G is 4-tough and H contains at least one edge, then $G°H$ is pancyclic. In addition, they showed the following theorem.

Theorem 9.

[7] If G, H are graphs with at least one edge each, then $G°H$ either has no cycles, or it contains cycles of all lengths between the length of the shortest cycle and the length of the longest cycle.

The following theorem on vertex pancyclic will be used in this article.

Theorem 10.

[5] Let G be a graph of order $n\ge 4$ with $d(u)+d(v)\ge n$ for distinct nonadjacent vertices u, v in G. Then, G is vertex 4-pancyclic unless n is even and $G=K_{n/2,n/2}.$

We know that a vertex pancyclic graph is hamiltonian. Then, a non-hamiltonian graph is not vertex pancyclic. Here, we provide the necessary condition for a graph to be hamiltonian as follows.

Theorem 11.

[11] If G has a hamiltonian cycle, then for each nonempty set $S\subseteq V$, the graph G – S has at most $\left|S\right|$ components.

To study vertex pancyclicity over lexicographic products, we start by investigating the lexicographic product of K_n with a graph G in Subsection 2.1. By Theorem 10, we obtain that $K_n°G$ is vertex pancyclic for $n\ge 3.$ In Subsection 2.2, we show that $G_1°G_2$ is vertex pancyclic if G₁ is a traceable graph of even order and G₂ is a graph with at least one edge. Since G₁ is traceble, we consider the lexicographic product of a path and G₂ instead of the lexicographic product of G₁ and G₂. Furthermore, we directly show that if G₁ and G₂ are nontrivial traceable graphs, then $G_1°G_2$ is vertex pancyclic. In Subsection 2.3, we show that if G₁ is hamiltonian and G₂ is a graph with at least one edge, then $G_1°G_2$ is vertex pancyclic. Since G₁ is hamiltonian, we consider the lexicographic product of a cycle and G₂ instead of the lexicographic product of G₁ and G₂.

2. Vertex pancyclicity of some lexicographic products

2.1. Complete Graphs

First of all, we investigate lexicographic products of complete graphs with a graph. Let K_n be a complete graph of order n and A_k be an empty graph of order k. Theorem 10 gives us the following theorem.

Theorem 12.

$K_n°A_k$ is vertex pancyclic for $n\ge 3$ and $k\ge 1.$

Proof.

Let (x, y) be any vertex of $K_n°A_k.$ Then, $N((x,y))=\underset{x\prime \in V(K_n)-\left\{x\right\}}{\cup }\{(x\prime ,y)|y\in V(A_k)\}.$ Since $n\ge 3,$ there are $x_i,x_j\in V(K_n)-\left\{x\right\}$ such that $x_i{x}_j\in E(K_n).$ Then, $(x,y)(x_i,y)(x_j,y)(x,y)$ forms a cycle of length 3 containing (x, y).

Next, we can see that the order of $K_n°A_k$ is nk and $|N((x,y))|=(n-1)k.$ Let $u,v\in V(K_n°A_k)$ such that $uv\notin E(K_n°A_k).$ Then, $d(u)+d(v)=2(n-1)k=2nk-2k\ge nk.$ Since $K_n°A_k$ is not isomorphic to a balance complete bipartite graph $K_{\frac{nk}{2},\frac{nk}{2}},$ by Theorem 10, we obtain that $K_n°A_k$ is vertex 4-pancyclic. Thus, (x, y) is contained in a cycle of each length l for $4\le l\le nk.$ Therefore, $K_n°A_k$ is vertex pancyclic. □

Since A_k is a spanning subgraph of all graphs of order k, we obtain the following corollary.

Corollary 1.

Let $n\ge 3$ and G be a graph. Then $K_n°G$ is vertex pancyclic.

By Corollary 1, since C₃ is a complete graph of order 3, we obtain the following corollary.

Corollary 2.

Let G be a graph. Then, $C_3°G$ is vertex pancyclic.

2.2. Paths

We start this section by considering the lexicographic product of a path P₂ and any graph as follows.

Let $P_2=x_1{x}_2$ and A_k be an empty graph of order k. Then, $P_2°A_k$ is isomorphic to a balanced complete bipartite graph $K_{k,k}$ with two partite sets, V₁ and V₂, where $V_1=\{(x_1,y)|y\in A_k\}$ and $V_2=\{(x_2,y)|y\in A_k\}.$

Since a balanced complete bipartite graph $K_{k,k}$ is hamiltonian and also vertex even pancyclic for $k\ge 2$ (to prove that $K_{k,k}$ is vertex even pancyclic, we can use the result that it is hamiltonian), we obtain that $P_2°A_k$ is vertex even pancyclic for $k\ge 2.$ Since A_k is a spanning subgraph of any graph of order k, we obtain the following remark.

Remark 1.

Let G be a nontrivial graph. Then, $P_2°G$ is vertex even pancyclic.

Now, we investigate the lexicographic product between P₂ and a graph G as follows.

Theorem 13.

Let G be a nontrivial graph with at least one edge. Then, $P_2°G$ is vertex pancyclic.

Proof.

Let $P_2=x_1{x}_2$ and $V(G)=\{y_1,y_2,y_3,\dots ,y_k\}$ for $k\ge 2.$ Since G contains at least one edge, assume that $y_1{y}_2\in E(G).$ Then, $(x_1,y_1)(x_1,y_2)$ and $(x_2,y_1)(x_2,y_2)$ are edges of $P_2°G.$ Let $(x,y)\in V(P_2°G).$ If x = x₁, then (x, y) is adjacent to both vertices (x₂, y₁) and (x₂, y₂). Thus, $(x,y)(x_2,y_1)(x_2,y_2)(x,y)$ is a cycle of length 3 containing (x, y). If x = x₂, then (x, y) is adjacent to both vertices (x₁, y₁) and (x₁, y₂). Thus, $(x,y)(x_1,y_1)(x_1,y_2)(x,y)$ is a cycle of length 3 containing (x, y). Thus, each vertex of $P_2°G$ is contained in a cycle of length 3.

Since $|E(G)|\ge 1,P_2°G$ is not isomorphic to any complete bipartite graph. Since $P_2°G$ is of order $2k\ge 4$ with $d(u)+d(v)\ge 2k$ for any pair of distinct nonadjacent vertices u and v in $P_2°G,$ by Theorem 10, G is vertex 4-pancyclic.

Therefore, $P_2°G$ is vertex pancyclic. □

Now, we consider the lexicographic product of a path P_n for $n\ge 2$ with a graph G.

Remark 2.

For any k and $n\ge 3,P_n°A_k$ is non-hamiltonian.

Let $P_n=x_1{x}_2{x}_3\cdots x_n$ and $V(A_k)=\{y_1,y_2,y_3,\dots ,y_k\}.$ Choose $S=\{(x_2,y)|y\in V(A_k)\}.$ Then, $\left|S\right|=k.$ Let H denote the graph $(P_n°A_k)-S.$ Then, H has k + 1 components, $H[(x_1,y_1)],H[(x_1,y_2)],H[(x_1,y_3)],\dots ,H[(x_1,y_k)]$ and $H[\{(x_i,y)|i\in \{3,4,5,\dots ,n\},y\in V(G)\}].$ By Theorem 11, $P_n°A_k$ is non-hamiltonian.

From Remark 2, we can see that the lexicographic product of P_n and an empty graph is non-hamiltonian and not vertex pancyclic. We invertigate the condition of a graph G for $P_n°G$ to be vertex pancyclic and show that $P_n°G$ is vertex pancyclic when n is even and G contains at least one edge. We start with the following lemmas.

Lemma 1.

Let $k\ge 2$. If u and v are on the different partite sets of a complete bipartite graph $K_{k,k}$, then there is a path P(u, v) in $K_{k,k}$ of each odd length l for $1\le l\le 2k-1.$

Proof.

Let $K_{k,k}$ be a complete bipartite graph for $k\ge 2$ with partite sets V₁ and V₂. Assume that $u\in V_1$ and $v\in V_2.$ For k = 2, let $u\prime \in V_1-\left\{u\right\}$ and $v\prime \in V_2-\left\{v\right\}.$ We obtain that uv and $uv\prime u\prime v$ are paths P(u, v) of length 1 and 3, respectively.

For $k\ge 3,$ let $V_1^{*}=V_1-\left\{u\right\}$ and $V_2^{*}=V_2-\left\{v\right\}.$ We can see that $K_{k-1,k-1}$ is a subgraph of $K_{k,k}$ induced by $V_1^{*}\cup V_2^{*}.$ Since a balanced complete bipartite graph is vertex even pancyclic, $K_{k-1,k-1}$ contains a cycle of each even length l for $4\le l\le 2(k-1).$ Let $C=v_1{v}_2{v}_3\cdots v_l{v}_1$ be a cycle in $K_{k-1,k-1}$ of even length l for some $4\le l\le 2(k-1).$ Then, any two consecutive vertices of C contain in the different partite sets. Without loss of generality, let $v_1\in V_1^{*}$ and $v_2\in V_2^{*}.$ We see that $v_i\in V_1^{*}$ if i is odd and $v_i\in V_2^{*}$ if i is even and $v_{1}v,v_{2}u\in E(K_{k,k}).$ Then, $u{v}_2{v}_3\cdots v_l{v}_{1}v$ is a path P(u, v) in $K_{k,k}$ of length l + 1. Note that l + 1 is an odd number. Since l is an arbitrary even number between 4 and $2(k-1),$ there exists a path P(u, v) in $K_{k,k}$ of each odd length l for $5\le l\le 2k-1.$ In addition, uv and $u{v}_2{v}_{1}v$ are paths from u to v in $K_{k,k}$ of length 1 and 3, respectively.

Therefore, there exists a path P(u, v) in $K_{k,k}$ of each odd length l for $1\le l\le 2k-1.$ □

Lemma 2.

Let $n\ge 2$ be even and G be a nontrivial graph of order k. If $P_n=x_1{x}_2{x}_3\cdots x_n$ is a path and $y_1{y}_2\in E(G)$, then $P_n°G$ contains a path $P((x_1,y_1),(x_1,y_2))$ of each length l for $1\le l\le nk-1.$

Proof.

Let $P_n=x_1{x}_2{x}_3\cdots x_n$ and $V(G)=\{y_1,y_2,y_3,\dots ,y_k\}$ for $k\ge 2.$ Since $y_1{y}_2\in E(G),$ vertices $(x_1,y_1),(x_1,y_2),(x_2,y_1)$ and (x₂, y₂) form a clique of order 4. Then, there are paths $P((x_1,y_1),(x_1,y_2))$ of length l for $1\le l\le 3.$

We prove by the mathematical induction on n. For n = 2, let $V_1^{*}=\{(x_1,y)|y\in V(G)-\left\{y_1\right\}\}$ and $V_2^{*}=\{(x_2,y)|y\in V(G)-\left\{y_1\right\}\}.$ We can see that the subgraph induced by $V_1^{*}\cup V_2^{*}$ in $P_n°G$ is isomorphic to $K_{k-1,k-1}.$ Since $(x_1,y_2)\in V_1^{*}$ and $(x_2,y_2)\in V_2^{*},$ by Lemma 1, there exists a path $P((x_1,y_2)(x_2,y_2))$ in $K_{k-1,k-1}$ of each odd length l for $1\le l\le 2(k-1)-1.$ To show that there exists a path $P((x_1,y_1),(x_1,y_2))$ of each length l for $1\le l\le 2k-1,$ we extend the path $P((x_1,y_2),(x_2,y_2))$ of each length l for $1\le l\le 2k-3$ as follows.

1. Join the vertex (x₁, y₁) with the vertex (x₂, y₂) of $P((x_1,y_2),(x_2,y_2))$ (see Figure 1(a)).

   Figure 1. (a) Joining vertex (x₁, y₁) to a path $P((x_1,y_2),(x_2,y_2))$ and (b) joining the edge $(x_1,y_1)(x_2,y_1)$ to a path $P((x_1,y_2),(x_2,y_2)).$

   

2. Join the vertex (x₂, y₁) of the edge $(x_1,y_1)(x_2,y_1)$ with the vertex (x₂, y₂) of $P((x_1,y_2),(x_2,y_2))$ (see Figure 1(b)).

Then, a path $P((x_1,y_2),(x_2,y_2))$ of each odd length l for $1\le l\le 2k-3$ can be extended to a path $P((x_1,y_1),(x_1,y_2))$ of each even length l for $2\le l\le 2k-2$ by (a), and of each odd length l for $3\le l\le 2k-1$ by (b). Thus, we obtain that there exists a path $P((x_1,y_1),(x_1,y_2))$ of each length l for $1\le l\le 2k-1.$

For the induction step, let $t\in \mathbb{N}$ and suppose that the statement holds for all even n, $n\le 2t.$ We show that the statement still holds for $n=2t+2.$ Let $V_i=\{(x_i,y)|y\in V(G)\}$ for $i\in \{1,2,3,\dots ,2t+2\}.$ The set ${\cup }_{i=1}^{2t}{V}_i$ induces a subgraph $P_{2t}°G$ of $P_{2t+2}°G.$ By the induction hypothesis, $P_{2t+2}°G$ contains paths $P((x_1,y_1),(x_1,y_2))$ of each length l for $1\le l\le 2tk-1.$ In order to show that there exists a path $P((x_1,y_1),(x_1,y_2))$ of each length l for $2tk\le l\le (2t+2)k-1,$ we preform three steps as follows.

1. We show that there is a path $P((x_{2t},y_2),(x_1,y_2))$ of length $2t(k-1)-1.$ Let $V_i^{*}=\{(x_i,y)|y\in V(G)-\left\{y_1\right\}\}$ for all $i\in \{1,2,3,\dots ,2t\}.$ Consider each pair of vertex set $V_{2j-1}^{*}$ and $V_{2j}^{*}$ for all $j\in \{1,2,3,\dots ,t\}.$ We can see that the set $V_{2j-1}^{*}\cup V_{2j}^{*}$ induces a subgraph $K_{k-1,k-1}$ of $P_n°G.$ By Lemma 1, there is a path $P((x_{2j-1},y_2),(x_{2j},y_2))$ of length $2k-3.$ We connect such t paths, $P((x_{2j-1},y_2),(x_{2j},y_2))$ for all $j\in \{1,2,3,\dots ,t\},$ together to obtain a path $P((x_1,y_2),(x_{2t},y_2))$ of length $2t(k-1)-1.$ By reversing path $P((x_1,y_2),(x_{2t},y_2)),$ there is a path $P((x_{2t},y_2),(x_1,y_2))$ of length $2t(k-1)-1$ (see Figure 2(a)).

   Figure 2. (a) A path $P((x_{2t},y_2),(x_1,y_2))$ and (b) a path $P((x_1,y_1),(x_{2t},y_2))$ of length $2t+1.$

   

2. We show that there is a path $P((x_1,y_1),(x_1,y_2))$ of length 2tk. From (i), there is $P((x_{2t},y_2),(x_1,y_2))$ of length $2t(k-1)-1$ and $P((x_1,y_1),(x_{2t},y_2)):(x_1,y_1)(x_2,y_1)(x_3,y_1)\cdots (x_{2t},y_1)(x_{2t+1},y_1)(x_{2t},y_2)$ is a path of length $2t+1$ (see Figure 2(b)). Connecting $P((x_{2t},y_2),(x_1,y_2))$ and $P((x_1,y_1),(x_{2t},y_2))$ together yields a path $P((x_1,y_1),(x_1,y_2))$ of length 2tk.

3. We show that there is a path $P((x_1,y_1),(x_1,y_2))$ of each length l for $2tk+1\le l\le (2t+2)k-1.$ Let $P((x_1,y_1),(x_{2t},y_1)):(x_1,y_1)(x_2,y_1)(x_3,y_1)\cdots (x_{2t},y_1)$ be a path of length $2t-1.$ By connecting $P((x_1,y_1),(x_{2t},y_1))$ with $P((x_{2t},y_2),(x_1,y_2))$ of length $2t(k-1)-1$ from (i). We obtain a path $P^{*}((x_1,y_1),(x_1,y_2))$ of length $2tk-1$ (see Figure 3(a)). Consider the set $V_{2t+1}\cup V_{2t+2}.$ The set $V_{2t+1}\cup V_{2t+2}$ induces a subgraph $P_2°G$ of $P_{2t+2}°G.$ By the induction hypothesis, $P_{2t+2}°G$ contains a path $P((x_{2t+1},y_1),(x_{2t+1},y_2))$ of each length l for $1\le l\le 2k-1$ where each vertex of $P((x_{2t+1},y_1),(x_{2t+1},y_2))$ contains in the set $V_{2t+1}\cup V_{2t+2}$ (see Figure 3(b)). Since $(x_{2t+1},y_1)$ and $(x_{2t+1},y_2)$ are adjacent to vertices $(x_{2t},y_1)$ and $(x_{2t},y_2),$ we replace the edge $(x_{2t},y_1)(x_{2t},y_2)$ of $P^{*}((x_1,y_1),(x_1,y_2))$ by $P((x_{2t+1},y_1),(x_{2t+1},y_2))$ of each length l for $1\le l\le 2k-1$ and obtain a path $P((x_1,y_1),(x_1,y_2))$ of each length l for $2tk+1\le l\le (2t+2)k-1.$

   Figure 3. (a) A path $P^{*}((x_1,y_1),(x_1,y_2))$ of length $2tk-1$ and (b) a path $P((x_{2t+1},y_1),(x_{2t+1},y_2)).$

   

Therefore, there exist paths $P((x_1,y_1),(x_1,y_2))$ of each length l for $1\le l\le nk-1$ for n is an even number $n\ge 2.$ □

By reversing path $P_n:x_1{x}_2{x}_3\cdots x_n$ into $x_n{x}_{n-1}{x}_{n-2}\dots x_1,$ we also obtain that $P_n°G$ contains a path $P((x_n,y_1),(x_n,y_2))$ between $(x_n,y_1)$ and $(x_n,y_2)$ of each length l for $1\le l\le nk-1$ when n is even.

Theorem 14.

Let $n\ge 2$ be even. If G is a graph with at least one edge, then $P_n°G$ is vertex pancyclic.

Proof.

Let $P_n=x_1{x}_2{x}_3\cdots x_n$ and $V(G)=\{y_1,y_2,y_3,\dots ,y_k\}$ for $k\ge 2.$ Since G contains at least one edge, without loss of generality, we assume that $y_1{y}_2\in E(G).$

We prove by the mathematical induction on n. For n = 2, Theorem 13 yileds that $P_2°G$ is vertex pancyclic.

For the induction step, let $t\in \mathbb{N}$ and suppose that the statement holds for all even n, where $n\le 2t.$ We show that the statement still holds for $n=2t+2.$ Let $V_i=\{(x_i,y)|y\in V(G)\}$ for $i\in \{1,2,3,\dots ,2t+2\}.$ The each set, ${\cup }_{i=1}^{2t}{V}_i$ and ${\cup }_{i=2}^{2t+2}{V}_i,$ induces a subgraph $P_{2t}°G$ of $P_{2t+2}°G.$ By the induction hypothesis, a vertex in the induced subgraph $P_{2t}°G$ is contained in a cycle of each length l for $3\le l\le 2tk.$ Then, all vertices of $P_{2t+2}°G$ is contained in a cycle of each length l for $3\le l\le 2tk.$ In order to show that $P_{2t+2}°G$ is vertex pancyclic, we show that each vertex of $P_{2t+2}°G$ is contained in a cycle of each length l for $2tk+1\le l\le (2t+2)k.$

Let (x, y) be a vertex of $P_n°G.$ Without loss of generality, we assume that $(x,y)\in {\cup }_{i=1}^{2t}{V}_i.$ We perform two steps as follows.

1. We show that there is a cycle of length $2tk+1$ containing (x, y). By Lemma 2 and the reversing path, there is a path $P((x_{2t},y_1),(x_{2t},y_2))$ of length $2tk-1$ in the subgraph of $P_{2t+2}°G$ induced by ${\cup }_{i=1}^{2t}{V}_i.$ Moreover, $P((x_{2t},y_1),(x_{2t},y_2))$ contains vertex (x, y). Since vertex $(x_{2t+1},y_1)$ is adjacent to the two end verties of $P((x_{2t},y_1),(x_{2t},y_2)),$ we connect $(x_{2t+1},y_1)$ to each end vertex of $P((x_{2t},y_1),(x_{2t},y_2)).$ Then, a cycle of length $2tk+1$ containing (x, y) is obtained.

2. We show that there is a cycle of each length l for $2tk+2\le l\le (2t+2)k$ containing (x, y). We can see that $P_2°G$ is the subgraph of $P_{2t+2}°G$ induced by $V_{2t+1}\cup V_{2t+2}.$ By Lemma 2, there is a path $P((x_{2t+1},y_1),(x_{2t+1},y_2))$ in $P_2°G$ of each length l for $1\le l\le 2k-1.$ For the subgraph of $P_{2t}°G$ of $P_{2t+2}°G$ induced by ${\cup }_{i=1}^{2t}{V}_i,$ we obtain (from Lemma 2 and the reversing path) a path $P((x_{2t},y_1),(x_{2t},y_2))$ of length $2tk-1$ containing (x, y). Since $(x_{2t+1},y_1)$ and $(x_{2t+1},y_2)$ are adjacent to $(x_{2t},y_1)$ and $(x_{2t},y_2),$ respectively, we connect each end vertex of $P((x_{2t+1},y_1),(x_{2t+1},y_2))$ to each end vertex of $P((x_{2t},y_1),(x_{2t},y_2))$ together. Then, (x, y) is contained in a cycle of each length l for $2tk+2\le l\le (2t+2)k.$

Therefore, $P_n°G$ is vertex pancyclic for n is even. □

By Theorem 14, we obtain that $P_n°G$ is vertex pancyclic if n is even and G is a graph with at least one edge. Since a path P_n is a subgraph of traceable graphs of order n, we obtain the following corollary.

Corollary 3.

If G₁ is a traceable graph of even order and G₂ is a graph with at least one edge, then $G_1°G_2$ is vertex pancyclic.

Example 1.

Petersen graph is a graph of order 10 containing a hamiltonian path. By Corollary 3, the lexicographic product of this Petersen graph with a graph of at least one edge is vertex pancyclic.

Next, we investigate the lexicographic product of odd paths and a graph.

Theorem 15.

Let n > 2 be odd. If G is a graph of order $k>\frac{n+1}{2}$ with exactly one edge, then $P_n°G$ is not vertex pancyclic.

Proof.

Let $P_n=x_1{x}_2{x}_3\cdots x_n$ and $V(G)=\{y_1,y_2,y_3,\dots ,y_k\}$ where $k>\frac{n+1}{2}.$ Assume that $E(G)=\left\{y_1{y}_2\right\}.$ Choose $S=\underset{i\in \{2,4,6,\dots ,n-1\}}{\cup }\{(x_i,y)|y\in V(G)\}.$ Then, $\left|S\right|=k\left(\frac{n-1}{2}\right).$ Let H denote the graph $(P_n°G)-S.$ Then, H has $(k-1)\left(\frac{n+1}{2}\right)$ components, $H[\{(x_i,y_1),(x_i,y_2)\}],H[(x_i,y_3)],H[(x_i,y_4)],\dots ,H[(x_i,y_k)]$ for all $i\in \{1,3,5,\dots ,n\}.$ By Theorem 11, $P_n°G$ is non-hamiltonian. Therefore, $P_n°G$ is not vertex pancyclic. □

Therefore, if n is odd and G is a graph with the same condition as in Theorem 14, i.e.,G is a graph with at least one edge, then we cannot conclude anything about vertex pancyclic of $P_n°G.$

Now, we investigate the condition that provide vertex pancyclic over lexicographic products. We consider nontrivial traceable graphs G₁ and G₂ as follows.

Theorem 16.

If G₁ and G₂ are nontrivial traceable graphs, then $G_1°G_2$ is vertex pancyclic.

Proof.

Let G₁ and G₂ be traceable graphs of order n and m, respectively, for $n,m\ge 2.$ Let $P_n:x_1{x}_2{x}_3\cdots x_n$ and $P_m:y_1{y}_2{y}_3\cdots y_m$ be spanning paths in G₁ and G₂, respectively. Since G₂ is a nontrivial traceable graph, G₂ contains at least one edge.

If n is even, by Corollary 3, $G_1°G_2$ is vertex pancylic. Assume that n is odd. Let $P_{n-1}:x_1{x}_2{x}_3\cdots x_{n-1}$ and $P_{n-1}^{*}:x_2{x}_3{x}_4\cdots x_n$ be subgraphs of P_n. We can see that $P_{n-1}°G_2$ and $P_{n-1}^{*}°G_2$ are subgraphs of $G_1°G_2.$ By Theorem 14, $P_{n-1}°G_2$ and $P_{n-1}^{*}°G_2$ are vertex pancyclic. Then, each vertex of $G_1°G_2$ is contained in a cycle of each length l for $3\le l\le k(n-1).$

We show that each vertex of $G_1°G_2$ is contained in a cycle of each length l for $(n-1)k+1\le l\le nk.$ Let (x_i, y_j) be a vertex of $G_1°G_2$ for some $i\in \{1,2,3,\dots ,n\}$ and $j\in \{1,2,3,\dots m\}.$

Case 1. $i\in \{1,2,3,\dots ,n-1\}.$ Then, we consider the subgraph $P_{n-1}°G_2.$ Similar to the prove of Theorem 14, by reversing a path $P_{n-1}$ of Lemma 2, there is a path $P((x_{n-1},y_1),(x_{n-1},y_2))$ of length $(n-1)k-1$ containing vertex (x_i, y_j). Consider subgraph $\left\{x_n\right\}°G_2$ of $G_1°G_2.$ This subgraph contains a path $P((x_n,y_1),(x_n,y_j)):(x_n,y_1)(x_n,y_2)(x_n,y_3)\cdots (x_n,y_j)$ where $j\in \{1,2,3,\dots ,k\}.$ Since each vertex of $P((x_n,y_1),(x_n,y_j))$ is adjacent to vertices $(x_{n-1},y_1)$ and $(x_{n-1},y_2),$ we connect $P((x_{n-1},y_1),(x_{n-1},y_2))$ with each end vertex of $P((x_n,y_1),(x_n,y_j)),$ respectively, for all $j\in \{1,2,3,\dots ,k\}.$ Then, (x_i, y_j) is contained in a cycle of length l for $(n-1)k+1\le l\le nk.$

Case 2. i = n. We consider the subgraph $P_{n-1}^{*}°G_2$ instead of $P_{n-1}°G.$ By Lemma 2, there is a path $P((x_2,y_1),(x_2,y_2))$ of length $(n-1)k-1$ containing vertex (x_i, y_j). Consider subgraph $\left\{x_1\right\}°G_2$ of the lexicographic product $G_1°G_2.$ It contains a path $P((x_1,y_1),(x_1,y_j)):(x_1,y_1)(x_1,y_2)(x_1,y_3)\cdots (x_1,y_j)$ where $j\in \{1,2,3,\dots ,k\}.$ By a similar argument as in case 1, we obtain that (x_i, y_j) is contained in a cycle of each length l for $(n-1)k+1\le l\le nk.$

Therefore, $G_1°G_2$ is vertex pancyclic. □

By Theorem 16, we obtain that $P_n°P_2$ is vertex pancyclic for all $n\ge 2$ even though n is an odd number, the following theorem is proved.

Corollary 4.

If G is a nontrivial traceable graph, then the double graph of G is vertex pancyclic.

2.3. Cycles

Theorem 17.

Let $n\ge 3,k\ge 1$ and A_k be an empty graph of order k. Then, $C_n°A_k$ is hamiltonian.

Proof.

We see that $C_n°A_1$ is C_n which is hamiltonian. Assume that k > 1. Let $C_n:x_1{x}_2{x}_3\cdots x_n{x}_1$ and $V(A_k)=\{y_1,y_2,y_3,\dots ,y_k\}.$ We can see that the path $x_1{x}_2{x}_3\cdots x_n$ in C_n forms the path $P_i:(x_1,y_i)(x_2,y_i)(x_3,y_i)\cdots (x_n,y_i)$ in $C_n°A_k$ for each $i\in \{1,2,3,\dots ,k\}.$ Let $e_i=(x_n,y_i)(x_1,y_{i+1})$ for $i\in \{1,2,3,\dots ,k-1\}$ and $e_k=(x_n,y_k)(x_1,y_1).$ For $i\in \{1,2,3,\dots ,k-1\},$ each pair of paths P_i and $P_{i+1}$ is connected by the edge e_i and the paths P_k and P₁ are connected by the edge e_k. A hamiltonian in $C_n°A_k$ is $$P_1{e}_1{P}_2{e}_2{P}_3{e}_3\cdots e_{k-1}{P}_k{e}_k.$$

□

Since $C_n°A_k$ is a subgraph of $C_n°G$ for any graph G of order k, we obtain the following corollaries.

Corollary 5.

If $n\ge 3$ and G is a graph, then $C_n°G$ is hamiltonian.

Corollary 6.

If G₁ is hamiltonian and G₂ is a graph, then $G_1°G_2$ is hamiltonian.

Corollary 6 does not hold for the cartesian product $G_1\square G_2.$ For counter example, let G₂ be disconnected. Then, $G_1\square G_2$ is disconnected (and of course non-hamiltonian) although G₁ is hamiltonian.

By Corollary 2, $C_3°A_k$ is vertex pancyclic for $k\ge 1.$ Unfortunately, the lexicographic product of cycle C_n for $n\ge 4$ and empty graph A_k for $k\ge 1$ is not vertex pancyclic. For instance, $C_7°A_2$ contains no cycle of length 5. Now, we investigate the condition of G that allows the product $C_n°G$ to be vertex pancyclic.

Theorem 18.

Let $n\ge 3$. If G is a graph with exactly one edge, then $C_n°G$ is vertex pancyclic.

Proof.

Let $C_n:x_1{x}_2{x}_3\cdots x_n{x}_1$ and $V(G)=\{y_1,y_2,y_3,\dots ,y_k\}$ for $k\ge 2.$ Since G contains exactly one edge, assume that $y_1{y}_2\in E(G).$ We can see that $P_n°G$ is a spanning subgraph of $C_n°G$ where $P_n:x_1{x}_2{x}_3\cdots x_n.$ By Theorem 14, $C_n°G$ is vertex pancyclic if n is even.

Assume that n is odd. Let $P_{n-1}:x_1{x}_2{x}_3\cdots x_{n-1}$ and $P_{n-1}^{*}:x_2{x}_3{x}_4\cdots x_n.$ We can see that $P_{n-1}°G$ and $P_{n-1}^{*}°G$ are subgraphs of $C_n°G$ induced by $V((P_n-x_n)°G)$ and $V((P_n-x_1)°G),$ respectively. By Theorem 14, $P_{n-1}°G$ and $P_{n-1}^{*}°G$ are vertex pancyclic. Then, each vertex of $C_n°G$ is contained in a cycle of each length l such that $3\le l\le (n-1)k.$

We now apply Theorem 9 to show that each vertex is contained in a cycle of each length l such that $(n-1)k+1\le l\le nk.$

By Theorem 9 and Corollary 5, $C_n°G$ contains a cycle of each length l such that $3\le l\le nk.$ Let $C_l:(x_{i_1},y_{j_1})(x_{i_2},y_{j_2})(x_{i_3},y_{j_3})\cdots (x_{i_l},y_{j_l})(x_{i_1},y_{j_1})$ be a cycle in $C_n°G$ of length l for some $(n-1)k+1\le l\le nk,$ for $\alpha \in \{1,2,3,\dots l\},$ $i_{\alpha }\in \{1,2,3,\dots ,n\}$ and $j_{\alpha }\in \{1,2,3,\dots ,k\}.$ We consider two cases as follows.

Case 1. $y_1{y}_2$ does not form an edge in C_l. Then, C_l is a cycle in $C_n°A_k.$ Let (x_s, y_t) be a vertex of $C_n°G$ where $s\in \{1,2,3,\dots ,n\}$ and $t\in \{1,2,3,\dots ,k\}.$ If $(x_s,y_t)=(x_{i_{\alpha }},y_{j_{\alpha }})$ for some $\alpha \in \{1,2,3,\dots l\},$ then (x_s, y_t) is contained in C_l. Assume that $(x_s,y_t)\ne (x_{i_{\alpha }},y_{j_{\alpha }})$ for any α. We consider two subcases as follows.

Subcase 1.1. If $x_s=x_{i_{\beta }}$ for some $\beta \in \{1,2,3,\dots l\},$ then $(x_s,y_{j_{\beta }})=(x_{i_{\beta }},y_{j_{\beta }})\in C_l.$ Since C_l is in $C_n°A_k,x_{i_{\alpha }}\ne x_{i_{\alpha +1}}$ for any $\alpha \in \{1,2,3,\dots l-1\}$ and $x_{i_l}\ne x_{i_1}.$ This implies that $x_{i_{\beta -1}}{x}_{i_{\beta }},x_{i_{\beta }}{x}_{i_{\beta +1}}\in E(C_n).$ Since $x_s=x_{i_{\beta }},(x_{i_{\beta -1}},y_{j_{\beta -1}})(x_s,y_t),(x_s,y_t)(x_{i_{\beta +1}},y_{j_{\beta +1}})$ $\in E(C_n°G).$ Thus, we can replace $(x_{i_{\beta }},y_{j_{\beta }})$ in C_l by (x_s, y_t). Therefore, (x_s, y_t) is contained in a cycle of length l.

Subcase 1.2. If $x_s\ne x_{i_{\alpha }}$ for all $\alpha \in \{1,2,3,\dots l\},$ we translate cycle C_l to be $C_l^{*}$ by defining an injective function. Let $i_w=\max \left\{i_{\alpha }\right|(x_{i_{\alpha }},y_{j_{\alpha }})\in C_l\}.$ We define an injective function $\phi :\{1,2,3,\dots ,n\}\to {\mathbb{Z}}_n$ by $\phi (i_{\alpha })=(i_{\alpha }+s-i_w)(\text{mod} n).$ This function translates indices in each vertex $(x_{i_{\alpha }},y_{j_{\alpha }})$ of the cycle C_l. The vertices with new indices are vertices of cycle $C_l^{*}.$ From this function, vertex $(x_{i_w},y_{j_w})$ is translate into vertex $(x_s,y_{j_w}).$ If $y_t=y_{j_w},$ then $(x_s,y_t)=(x_s,y_{j_w})$ is contained in $C_l^{*}.$ Assume that $y_t\ne y_{j_w}.$ We can replace vertex $(x_s,y_{j_w})$ by vertex (x_s, y_t) as showed in Subcase 1.1. Hence, (x_s, y_t) is contained in a cycle of length l.

Case 2. $y_1{y}_2$ forms an edge in C_l. Let S be a subgraph of G induced by the set $\{y_1,y_2\}.$ Then, S is a path $y_1{y}_2.$ If k = 2, then $C_n°G=C_n°P_2.$ By Theorem 4, $C_n°G$ is vertex pancyclic. Now, we assume that k > 2. Let ${\mathbb{S}}_1$ and ${\mathbb{S}}_2$ be subgraphs of $C_n°G$ induced by $P_n°S$ and $P_n°(G-S),$ respectively. Then, $V({\mathbb{S}}_1)=\{(x_i,y_j)|i\in \{1,2,3,\dots n\} \text{and} j\in \{1,2\}\}$ and $V({\mathbb{S}}_2)=\{(x_i,y_j)|i\in \{1,2,3,\dots n\} \text{and} j\in \{3,4,5,\dots ,k\}\}.$ We can see that $V(C_n°G)=V({\mathbb{S}}_1)\cup V({\mathbb{S}}_2).$

We first show that all vertices of ${\mathbb{S}}_1$ are contained in a cycle of length l. Since $y_1{y}_2$ forms an edge in C_l, C_l contains a vertex of ${\mathbb{S}}_1.$ Then, there are vertices $(x_i,y_1)$ and $(x_i,y_2)$ contained in C_l for some $i\in \{1,2,3,\dots ,n\}.$ We translate cycle C_l into $C_l^{*},$ as showed in Subcase 1.2, and obtain that all vertices in ${\mathbb{S}}_1$ are contained in a cycle of length l.

Next, we show that each vertex of ${\mathbb{S}}_2$ is contained in a cycle of length l. Consider a cycle of maximum length in ${\mathbb{S}}_1.$ The length of such cycles is at most 2n. Since the length of C_l is at least $(n-1)k+1$ and $(n-1)k+1>2n$ for k > 2, the cycle C_l contains a vertex of ${\mathbb{S}}_2.$ Let (x_s, y_t) be any vertex in $C_n°{\mathbb{S}}_2.$ If $(x_s,y_t)=(x_{i_{\alpha }},y_{j_{\alpha }})$ for some $\alpha \in \{1,2,3,\dots ,l\},$ then $(x_s,y_t)\in C_l.$ Assume that $(x_s,y_t)\ne (x_{i_{\alpha }},y_{j_{\alpha }})$ for any $\alpha \in \{1,2,3,\dots ,l\}.$ If $x_s=x_{i_{\beta }}$ for some $i_{\beta }\in \left\{i_{\alpha }\right|(x_{i_{\alpha }},y_{j_{\alpha }})\in {\mathbb{S}}_2\},$ then $(x_{i_{\beta }},y_{j_{\beta }})\in C_l.$ Similar to Subcase 1.1, we can replace vertex $(x_{i_{\beta }},y_{j_{\beta }})$ by (x_s, y_t). Thus, (x_s, y_t) is in a cycle of length l. If $x_s\ne x_{i_{\beta }}$ for all $i_{\beta }\in \left\{i_{\alpha }\right|(x_{i_{\alpha }},y_{j_{\alpha }})\in {\mathbb{S}}_2\},$ then let $i_w=\max \left\{i_{\alpha }\right|(x_{i_{\alpha }},y_{j_{\alpha }})\in {\mathbb{S}}_2\}.$ Similar to Subcase 1.2, we can translate cycle C_l into $C_l^{*}.$ Then, vertex $(x_{i_w},y_{j_w})$ is translated into $(x_s,y_{j_w}).$ If $y_t=y_{j_w},$ then (x_s, y_t) is contained in $C_l^{*}.$ Otherwise, we can replace vertex $(x_s,y_{j_w})$ by (x_s, y_t) as shown in Subcase 1.1.

From these two cases, we conclude that each vertex is contained in a cycle of each length l for $(n-1)k+1\le l\le nk.$ Therefore, $C_n°G$ is vertex pancyclic. □

From Theorem 18, we can see that adding more edges into the graph G dose not affect vertex pancyclic property. Thus, we obtain the following corollary.

Corollary 7.

Let $n\ge 3$. If G is a graph with at least one edge, then $C_n°G$ is vertex pancyclic.

If G₁ is hamiltonian containing a spanning cycle C_n, then C_n is a subgraph of G₁. We can extend Corollary 7 as follows.

Corollary 8.

If G₁ is hamiltonian and G₂ is a graph with at least one edge, then $G_1°G_2$ is vertex pancyclic.

3. Conclusion and discussion

This article obtain that $C_n°G$ is vertex pancyclic provided that $|E(G)|\ge 1$ and $n\ge 3$ and $K_n°G$ is vertex pancyclic for all positive integers n. However, the vertex pancyclicity of $P_n°G$ can be obtained only for $n\ge 2$ is an even integer. If n = 1, then $P_1°G=G.$ Thus, the vertex pancyclicity of $P_1°G$ depends on G. If $n\ge 3$ is an odd integer, then we can see from Theorem 15 that the vertex pancyclicity of $P_n°G$ may depend on some conditions on n and k. Therefore, our future research will try to find the conditions which imply the vertex pancyclicity of the $P_n°G$ when $n\ge 3$ is odd integer.