J.
Indones.
Math.
Soc.
Vol.
No.
, pp.
105Ae116.
EULERIAN AND HAMILTONIAN PROPERTIES OF
GALLAI AND ANTI-GALLAI TOTAL GRAPHS
Pravin Garg1 .
Deepa Sinha2 .
Shanu Goyal3 Department of Mathematics.
University of Rajasthan Jaipur-302004.
Rajasthan.
India pravin@gmail.
Department of Mathematics.
South Asian University Akbar Bhawan.
Chanakyapuri.
New Delhi-110021.
India deepa sinha2001@yahoo.
Department of Mathematics & Statistics.
Banasthali University Banasthali-304022.
Rajasthan.
India shanugoyalnewai@gmail.
Abstract.
Let G = (V.
E) be a graph.
The Gallai total graph eT (G) of G is the graph, where V .
T (G)) = V O E and uv OO E.
T (G)) if and only if .
u and v are adjacent vertices in G, or .
u is incident to v or v is incident to u in G, or .
u and v are adjacent edges in G which do not span a triangle in G.
The anti-Gallai total graph OIT (G) of G is the graph, where V (OIT (G)) = V O E and uv OO E(OIT (G)) if and only if .
u and v are adjacent vertices in G, or .
u is incident to v or v is incident to u in G, or .
u and v are adjacent edges in G and lie on a same triangle in G.
In this paper, we discuss Eulerian and Hamiltonian properties of Gallai and antiGallai total graphs.
Key words: Euler graph.
Hamiltonian graph.
Gallai total graph, anti-Gallai total 2010 Mathematics Subject Classification: 05C45, 05C76.
Received: 10-03-2015, revised: 22-09-2015, accepted: 29-09-2015.
Garg, et al.
Abstrak.
Misalkan G = (V.
E) adalah sebuah graf.
Graf total Gallai eT (G) dari G adalah sebuah graf dimana V .
T (G)) = V O E dan uv OO E.
T (G)) jika dan hanya jika .
u dan v adalah titik-titik bertetangga di G, atau .
u berkaitan dengan v atau v berkaitan dengan u di G, atau .
u dan v adalah sisi-sisi bertetangga di G yang tidak membangun suatu segitiga di G.
Graf total anti-Gallai OIT (G) dari G adalah sebuah graf dimana V (OIT (G)) = V OE dan uv OO E(OIT (G)) jika dan hanya jika .
u dan v adalah titik-titik bertetangga di G, atau .
u berkaitan dengan v atau v berkaitan dengan u di G, atau .
u dan v adalah sisi-sisi bertetangga di G dan terletak pada suatu segitiga di G.
Pada paper ini, kami meneliti sifat-sifat Euler and Hamilton dari graf total Gallai and anti-Gallai.
Kata kunci: Graf Euler, graf Hamilton, graf total Gallai, graf total anti-Gallai.
Introduction A graph G = (V.
E) is an ordered pair of set of vertices and edges, where edges are unordered pair of vertices.
Also G is said to be a .
, .
graph if |V | = p and |E| = q.
A graph is simple if it has neither self loop nor multiple edges.
A finite graph is a graph with finite number of vertices and edges.
Two vertices .
are said to be adjacent if they have a common edge .
If a vertex v lies on an edge e, then they are said to be incident to each other.
The degree d.
of a vertex v OO V is the number of edges incident at v.
A regular graph is the graph in which every vertex of the graph has same degree.
A path in a graph G is a walk with no repeated vertex.
A graph G is said to be connected if there exists a path between every pair of vertices of G.
Let G = (V.
E) be a graph with |V | = p, then the adjacency matrix A(G) of G is defined as A(G) = .
ij ]pyp , where 1 if vi is adjacent to vj , i 6= j, 0 otherwise.
A graph G is called Euler graph if there exists a closed walk in G with no repeated edge and all the edges are traversed exactly once.
A closed path is called a A cycle is said to be spanning cycle if it contains all the vertices of the graph.
A graph G is said to be Hamiltonian if it contains a spanning cycle.
Vertices and edges of G are called elements of G.
The line graph L(G) of a graph G is defined as the graph whose vertices are the edges of G, with two vertices adjacent in L(G) if and only if the corresponding edges are adjacent in G.
The line graphs were first studied by Whitney .
The line graph is the well studied graph operator in the literature .
, .
, .
Eulerian and Hamiltonian Properties of Gallai The Gallai graph e(G) of a graph G is the graph in which V .
(G)) = E(G) and two distinct edges of G are adjacent in e(G) if they are adjacent in G, but do not span a triangle in G.
The anti-Gallai graph OI(G) of a graph G is the graph in which V (OI(G)) = E(G) and two distinct edges of G are adjacent in OI(G) if they are adjacent in G and lie on a same triangle in G.
These constructions were used by Gallai .
in his investigation of comparability graphs.
the notion was suggested by Sun .
Sun used the Gallai graphs to describe a nice class of perfect graphs.
Gallai graphs are also used in polynomial time algorithm to recognize k1,3 -free perfect graphs by Chvatal and Sbihi .
Several properties of Gallai and anti-Gallai graphs are discussed in .
, .
, .
, .
, .
, .
Remark: A graph is triangle free if it does not contains a triangle.
If a graph G is triangle free, then e(G) O = L(G).
The total graph T (G) of G is the graph whose vertex set is V (G) O E(G), and two vertices are adjacent if and only if they are adjacent or incident in G.
The notion of total graph was introduced by Behzad and Chartrand .
Several properties of total graphs are investigated in the literature .
, .
, .
, .
Behzad obtained a characterization of total graphs in .
Gavril established a linear time algorithm for the recognition of the total graphs in .
Motivated from the operators Gallai graphs, anti-Gallai graphs and total graphs, we introduce two operators Gallai and anti-Gallai total graphs as follows:
Let G = (V.
E) be a graph.
The Gallai total graph eT (G) of G is the graph, where V .
T (G)) = V O E and uv OO E.
T (G)) if and only if .
u and v are adjacent vertices in G, or .
u is incident to v or v is incident to u in G, or .
u and v are adjacent edges in G which do not span a triangle in G.
The anti-Gallai total graph OIT (G) of G is the graph, where V (OIT (G)) = V O E and uv OO E(OIT (G)) if and only if .
u and v are adjacent vertices in G, or .
u is incident to v or v is incident to u in G, or .
u and v are adjacent edges in G and lie on a same triangle in G.
The Gallai total graph H = eT (G) and anti-Gallai total graph H 0 = OIT (G) of G are shown in Figure 1.
Degree of v OO V .
T (G)) and v OO V (OIT (G)) are denoted by de .
and dOI .
, respectively.
Throughout the paper, we consider simple and finite graphs.
Remark: If the graph G is triangle free, then eT (G) O = T (G).
Garg, et al.
HAo Figure 1.
A graph G, its Gallai total graph H = eT (G) and anti-Gallai total graph H 0 = OIT (G) Eulerian Gallai total graphs Proposition 2.
Let eT (G) be the Gallai total graph of a graph G = (V.
E), then 2d.
if v OO V (G), de .
= d.
1 ) d.
2 ) Oe 2t.
if v = v1 v2 OO E(G), where t denotes the number of triangles containing v in G.
Proof.
Let eT (G) be the corresponding Gallai total graph of G.
Since the graph G is a subgraph of eT (G) and also each edge incident to v in G is adjacent to corresponding vertex v in eT (G), therefore, de .
= 2d.
, for v OO V (G).
v = v1 v2 OO E(G), then the corresponding vertex v of eT (G) is adjacent to all the edges which are adjacent to v, but do not lie on a same triangle with v in G.
implies that they contribute the degree .
1 ) Oe .
2 ) Oe .
Oe 2t .
f v is the edge of a triangle, then it is not adjacent to those two edges of G which span a triangle with v in G) and v is also adjacent in eT (G) to the vertices by which it is incident in G, so 2 more degrees are also contributed, therefore, de .
= d.
1 ) d.
2 ) Oe 2t.
Lemma 2.
The number of triangles in a graph G is equal to tr(A , where A is the adjacency matrix of G.
Proposition 2.
Let G = (V.
E) be a .
, .
graph, then |E.
T (G))| = 2q tr(A3 ) Oe .
, where A is the adjacency matrix of G.
Proof.
Let G = (V.
E) be a .
, .
graph and v1 , v2 , .
, vi , .
, vp be vertices of G.
Then total degree of vertices of eT (G) is equal to 2 .
um of degree of the vertices of Eulerian and Hamiltonian Properties of Gallai G) sum of the degree of the vertices corresponding to the edges of G.
Let E 0 (G) be the set of edges which do not lie on a triangle in G and |E 0 (G)| = q1 .
Also let E 00 (G) be the set of edges which lie on a triangle in G and |E 00 (G)| = q2 .
Now if e = vi vj OO E 0 (G), then degree of the corresponding vertex e0 in eT (G) is equal to d.
i ) d.
j ), so the total degree of the vertices in eT (G) corresponding to such edges of G is .
i ) d.
j )).
If e = vi vj OO E 00 (G), then degree of the vi vj OOE 0 (G) corresponding vertex e0 in eT (G) is equal to d.
i ) d.
j ) Oe 2tij , where tij is the number of triangles on which the edge vi vj lies, so the total degree of the vertices in eT (G) corresponding to such edges of G is .
i ) d.
j ) Oe 2tij ).
Then vi vj OOE 00 (G) by handshake lemma on G and eT (G) we have, total degree of eT (G) 2.
i ) d.
j )) vi vj OOE 0 (G) .
i ) d.
j ) Oe 2tij ) vi vj OOE 00 (G) .
i ) d.
j )) Oe 2 .
ij ) vi vj OOE 00 (G) vi vj OOE(G) (.
i ))2 ) Oe 2.
y total no.
of triangles in G) .
i ))2 Oe 6.
umber of triangles in G) tr(A3 ) .
i )) Oe 6 , using Lemma 2.
Then by handshake lemma, the total number of edges in eT (G), .
i ))2 Oe 3 tr(A |E.
T (G))| = 2q 12 Proposition 2.
The Gallai total graph eT (G) of a graph G is regular if and only if G is regular and triangle free.
Proof.
Let G be a regular and triangle free graph.
Now we have to show that eT (G) is regular.
Since G is regular, degree of each vertex is same.
It implies that corresponding vertices of eT (G) are of same degree .
y the Proposition 2.
Also it is given that G is triangle free.
It follows that every vertex corresponding to the edges of G has degree d.
y the Proposition 2.
, where u and v are the end vertices of the edge and this is equal to 2d.
, being G is regular.
Therefore, degree of each vertex of eT (G) is same.
Hence, eT (G) is regular.
Conversely, suppose that eT (G) is regular.
Now we have to show that G is regular and triangle Garg, et al.
Let on contrary G is neither regular nor triangle free.
If G is not regular, then degree of every vertex of eT (G) corresponding to the vertices of G is not same, which is a contradiction to our fact that eT (G) is regular.
Hence G is regular.
Now if G is not triangle free, then degree of every vertex of eT (G) corresponding to the edges of G is d.
Oe 2t .
y the Proposition 2.
, where t is the number of triangles containing the edge, which is again a contradiction to our fact that eT (G) is regular.
Thus.
G is triangle free.
Hence.
G is regular and triangle free.
Proposition 2.
For a connected graph G, the Gallai total graph eT (G) has a spanning Eulerian subgraph.
Proof.
The result is obvious if G consists of a single vertex.
Otherwise, the connected spanning subgraph H of eT (G) obtained by deleting all the edges of the Gallai graph e(G), is Eulerian, since all its vertices have even degree.
Corollary 2.
For a connected graph G, enT (G) has a spanning Eulerian subgraph for all n Ou 1.
Proposition 2.
The Gallai total graph eT (G) of G is connected if and only if G is connected.
Proof.
Necessity: Let G be a connected graph.
By the Proposition 2.
5, eT (G) has a spanning Eulerian subgraph.
That means, there exists a path between every pair of vertices of eT (G).
Hence, eT (G) is connected.
Sufficiency: Suppose eT (G) is connected.
Now, we have to show that G is connected.
Let on contrary G be disconnected.
Then, there exists at least a pair of vertices which has no path between them.
Let u, v be two such vertices, then there is no path between u and v in eT (G).
It follows that eT (G) is disconnected, a contradiction to the hypothesis.
Hence the theorem.
Corollary 2.
The enT (G) of G is connected if and only if G is connected for all n Ou 1.
Parity of a vertex means parity of its degree, i.
degree of the vertex is either even or odd.
Theorem 2.
Let G be a connected graph, then the Gallai total graph eT (G) is Eulerian if and only if all the vertices of G are of the same parity.
Proof.
Let eT (G) be an Eulerian graph.
Assume to the contrary.
G has a vertex v1 with odd degree and a vertex v2 with even degree.
Since G is connected, v1 and v2 are joined by a path which contains two adjacent vertices vi and vj .
ot necessary different from v1 or v2 ) of opposite parity.
Thus, by the Proposition 2.
), the vertex in eT (G) which corresponds to the edge vi vj has odd degree, a contradiction to the fact that eT (G) is Eulerian.
Hence, all the vertices of G are Eulerian and Hamiltonian Properties of Gallai of the same parity.
Conversely, suppose all the vertices of G are of the same parity, then by the Proposition 2.
1, the vertices of eT (G) are of even degree.
Therefore, eT (G) is Eulerian.
Hence the theorem.
Corollary 2.
If G is Eulerian, then enT (G) is Eulerian for all n Ou 1, but converse is not true.
Counter example of converse: The Gallai total graph H = eT (G) of G is Eulerian, but G is not an Eulerian graph as shown in Figure 2.
Figure 2.
Eulerian Gallai total graph H = eT (G) of a non Eulerian graph G Eulerian anti-Gallai total graphs Proposition 3.
Let OIT (G) be the anti-Gallai total graph of a graph G = (V.
E), 2d.
if v OO V (G), dOI .
= 2t 2.
if v = v1 v2 OO E(G).
Garg, et al.
where t denotes the number of triangles containing v in G.
Proof.
Let OIT (G) be the corresponding anti-Gallai total graph of G.
Since the graph G is a subgraph of OIT (G) and also each edge incident to v in G is adjacent to corresponding vertex v in OIT (G), therefore, dOI .
= 2d.
, for v OO V (G).
v = v1 v2 OO E(G), then the corresponding vertex v of OIT (G) is adjacent to all the edges which are adjacent to v, and lie on a same triangle with v in G.
It implies they contribute the degree 2t .
f v is the edge of a triangle, then it is adjacent to those two edges of G which span triangle with v in G) and v is also adjacent in OIT (G) to the vertices by which it is incident in G, so 2 more degrees are also contributed, therefore, dOI .
= 2t 2.
Proposition Let G = (V.
E) be a .
, .
graph, then |E(OIT (G))| = 3q A is the adjacency matrix of G.
3 tr(A Proof.
Let G = (V.
E) be a .
, .
graph and v1 , v2 , .
, vi , .
, vp be vertices of G.
Then by the definition of OIT (G), sum of the degree of its vertices is equal to 2.
um of degree of the vertices of G) sum of the degree of the vertices corresponding to the edges of G.
If the edge e = vi vj does not lie on a triangle in G, then the degree of the corresponding vertex in OIT (G) is equal to 2, so the sum of the degree of the vertices corresponding to the edges of G is 2q .
is adjacent to vertices in OIT (G) corresponding to the vertices of G, by which it is inciden.
But if an edge lie on a triangle in G, then 2 degrees are increased, so if there is a triangle in G, then 6 degrees are increased.
Therefore, sum of the degree of the vertices of OIT (G) is 2.
umber of triangles in G) tr(A3 ) = 4q 2q 6 .
sing Lemma 2.
tr(A3 ) = 6q 6 By handshake lemma, the total number of edges in OIT (G), |E(OIT (G))| = 3q 3 tr(A A graph is called l-triangular if each edge of G lies on l number of triangles in G.
Proposition 3.
The anti-Gallai total graph OIT (G) of G is regular if and only if G is l-triangular and .
-regular.
Proof.
Suppose G is l-triangular and .
-regular.
Now we have to show that OIT (G) is regular.
Given that G is .
-regular, therefore the degree of every vertex in OIT (G) corresponding to the vertices of G are 2.
y the Proposition Also G is l-triangular.
It implies that the degree of every vertex of OIT (G) corresponding to the edges of G are 2l 2 .
y the Proposition 3.
Hence degree Eulerian and Hamiltonian Properties of Gallai of each vertex of OIT (G) is same.
Therefore.
OIT (G) is regular.
Conversely, suppose OIT (G) is regular.
Now we have to show that the given conditions are satisfied.
Let on contrary.
G be neither l-triangular nor .
If G is not .
-regular, then the degree of each vertex in OIT (G) corresponding to the vertices of G is not same, which is a contradiction to our fact that OIT (G) is regular.
Hence G is .
-regular.
Now, if G is not l-triangular, then the degree of the vertices corresponding to the edges of G are not same .
y the Proposition 3.
, which is a contradiction to our fact that OIT (G) is regular.
Thus.
G is l-triangular.
Hence G is l-triangular and .
-regular.
Proposition 3.
For a connected graph G, the anti-Gallai total graph OIT (G) has a spanning Eulerian subgraph.
Proof.
The result is obvious if G consists of a single vertex.
Otherwise, the connected spanning subgraph H of OIT (G) obtained by deleting all the edges of OI(G), is Eulerian, since all its vertices have even degree.
Corollary 3.
For a connected graph G.
OInT (G) has a spanning Eulerian subgraph for all n Ou 1.
Proposition 3.
The anti-Gallai total graph OIT (G) of G is connected if and only if G is connected.
Proof.
Suppose G is a connected graph, then by the Proposition 3.
OIT (G) has a spanning Eulerian subgraph.
That means, there exists a path between every pair of vertices of OIT (G).
Hence.
OIT (G) is connected.
Conversely, suppose OIT (G) is connected.
Now, we have to show that G is Let on contrary.
G be disconnected.
Then, there exists at least a pair of vertices which has no path between them.
Let u, v be two such vertices, then by the definition of OIT (G), u and v has no path in OIT (G).
It follows that OIT (G) is disconnected graph, a contradiction to the hypothesis.
Hence the theorem.
Corollary 3.
The anti-Gallai total graph OInT (G) of G is connected if and only if G is connected for all n Ou 1.
Theorem 3.
Let G be a connected graph, then OIT (G) of G is Eulerian.
Proof.
By the Proposition 3.
1, all the vertices of OIT (G) are of even degree and given that G is connected.
That means.
OIT (G) is Eulerian.
Corollary 3.
Let G be a connected graph, then OInT (G) of G is Eulerian.
Garg, et al.
Corollary 3.
If G is Eulerian, then OInT (G) of G is Eulerian, but converse is not true.
Counter example of converse: The anti-Gallai total graph OIT (G) of G is Eulerian, but G is not an Eulerian graph as shown in Figure 3.
Figure 3.
Eulerian anti-Gallai total graph H = OIT (G) of a non Eulerian graph G Hamiltonian Gallai and anti-Gallai total graphs Theorem 4.
The Gallai total graph eT (G) of a non-trivial graph G is Hamiltonian if and only if the set of all elements of G can be ordered in such a way that consecutive elements are neighbour as are the first and last elements, but the two edges are not consecutive elements, if both the edges are of same triangle.
Proof.
Let G be a graph.
The elements of G can be ordered in such a way that consecutive elements are neighbour as are the first and last elements, but the two edges are not consecutive elements, if both the edges are of same triangle.
Then by taking the corresponding vertices of eT (G) in the same order, a Hamiltonian cycle is produced.
Hence, eT (G) is Hamiltonian.
Conversely, let eT (G) be a Hamiltonian graph.
It follows that it contains a Hamiltonian cycle.
C = .
0 , v1 , .
, vm = v0 ).
Eulerian and Hamiltonian Properties of Gallai Let ai be that element of G associated with the vertex vi .
Thus, we get an ordering a0 , a1 , .
, amOe1 , am = a0 of elements of G.
By the definition of eT (G), this ordering is in such a way that consecutive elements are neighbour as are the first and last elements, but the two edges are not consecutive elements, if both the edges are of same triangle.
Hence the theorem.
Lemma 4.
If G is Hamiltonian, then its total graph T (G) is also Hamiltonian.
Corollary 4.
If G is Hamiltonian and triangle-free, then eT (G) is also Hamiltonian.
Theorem 4.
The anti-Gallai total graph OIT (G) of a non-trivial graph G is Hamiltonian if and only if the set of all elements of G can be ordered in such a way that consecutive elements are neighbour as are the first and last elements, but the two edges are not consecutive elements, if both the edges are not of same triangle.
Proof.
Let G be a graph.
The elements of G can be ordered in such a way that consecutive elements are neighbour as are the first and last elements, but the two edges are not consecutive elements, if both the edges are not of same triangle.
Then by taking the corresponding vertices of OIT (G) of G in the same order, a Hamiltonian cycle is produced.
Hence OIT (G) is Hamiltonian.
Conversely, let OIT (G) be a Hamiltonian graph.
It follows that it contains a Hamiltonian cycle.
C = .
0 , v1 , .
, vm = v0 ).
Let ai be that element of G associated with the vertex vi .
Thus, we get an ordering a0 , a1 , .
, amOe1 , am = a0 of elements of G.
By the definition of OIT (G), this ordering is in such a way that consecutive elements are neighbour as are the first and last elements, but the two edges are not consecutive elements, if both the edges are not of same triangle.
Hence the theorem.
Concluding Remarks In this note, we have introduced the notion of Gallai and anti-Gallai total graphs, and have investigated the Eulerian and Hamiltonian properties of these graph operators.
Further, one can find other graph theoretic properties of these Acknowledgement.
The authors express their sincere thanks to the referee for his/her valuable remarks, corrections and suggestions which improve the quality of the research paper a lot.
Garg, et al.
REFERENCES