Research Article
Contribution to 1-quasi-total Graphs
Department of Mathematics, Guntur Engineering College, Guntur Dt., Andhra Pradesh, India
J. Venkateswara Rao
Department of Mathematics, Mekelle University Main Campus, Mekelle, Ethiopia
Harary (1972) made an aperture on the concept of total graphs. Later on Bondy and Murty (1976) studied the applications of graph theory. Afterward Devadass (1977) made his contribution on regular graphs. Michalak (1981) made an attempt on middle and total graphs with coarseness number equal to 1. Further, Kulli (1989) investigated on planar graphs. Deo (2001) made an extensive study on this concept. After a while West (2002) developed the concept of quasi-total graphs. Srinivasulu (2006) derived some results on total graphs. Further, Mishra and Chandrasekaran (2007) made a contribution on total graphs.
This paper develops some of the properties of 1-quasi-total graph. A graph G is k-regular of d(v) = k for all v∈V; a regular graph is one that is k-regular for some k (Bondy and Murty, 1976). The chromatic number, χ(G), of G is the minimum k for which G is k- colourable; if χ(G) = k, G is said to be k- chromatic (Bondy and Murty, 1976; Deo, 2001). Unless otherwise mentioned all the graphs that we consider are finite graphs.
1-quasi-TOTAL GRAPHS
Definition 1: Let G be a graph with vertex set V(G) and edge set E(G). The 1-quasi-total graph (denoted by Q1(G)) of G is defined as follows: The vertex set of Q1(G) that is:
V(Q1(G)) = V(G)∪E(G) |
Two vertices x, y in V(Q1(G)) are adjacent if they satisfy one of the following conditions:
• | x, y are in V(G) and |
• | x, y are in E(G) |
• | x, y are incident in G |
where, G is a subgraph of Q1(G) and Q1(G) is a subgraph of T(G).
Fig. 1(a-b): | 1-quasi-total graph Q1(G) of graph G |
Example: Consider the graph G given in Fig. 1a. Let us construct the 1-quasi-total graph Q1(G) of the Fig. 1b:
V(Q1(G)) = {V(G)∪E(G)} = {v1, v2, v3, v4, e1, e2, e3, e4} |
We know that:
E(G)⊆E(Q1(G)) |
So, and ∈ E(Q1(G):
• | Since, e1 and e2 are incident in G, there is an edge ∈ E(Q1(G)) |
• | Since, e1 and e4 are incident in G, there is an edge ∈ E(Q1(G)) |
• | Since, e2 and e3 are incident in G, there is an edge ∈ E(Q1(G)) |
• | Since, e3 and e4 are incident in G, there is an edge ∈ E(Q1(G)) |
Therefore:
The 1-quasi-total graph Q1(G) is given by the Fig. 1b.
Theorem 1 : If G = (V, E) is a k- regular graph, then Q1(G) is a ring sum of exactly one k- regular graph G with |V| vertices and one 2(k-1) regular line graph with |E| vertices.
Proof: By the definition of Q1(G):
V(Q1(G)) = V(G)∪E(G) = V(G)∪V(L(G)) (since, V(L(G)) = E(G)) |
Let s∈E(G). If s is an edge in G, then s∈E(G). If s∉E(G), then (by the definition of Q1(G)), where e1, e2∈E(G) and e1, e2 are adjacent edges in G. By the definition of L(G) it follows that s∈E(L(G)). Therefore:
E(Q1(G))⊆E(G)∪E(L(G)) |
By Note 1, E(G)∪E(L(G))⊆E(Q1(G)). Now we proved that Q1(G) = G∪L(G), the union of the two graphs G and L(G). Since, V(G)∩V(L(G)) = V(G)∩E(G) = φ, there exists no common edge in G and L(G). This means that E(G)∩E(L(G)) = φ. This implies that G∪L(G) = G⊕L(G).
Hence, Q1(G) = G∪L(G) = G⊕L(G). We show that Q1(G) is a ring sum of K- regular graph G and one 2(k-1) regular line graph. By the above result it is enough to prove that G is regular and L(G) is 2(k-1) regular. By hypothesis G is k-regular. We have to show L(G) is 2(k-1) regular graph.
We have to prove degree of e∈ V(L(G)) is 2(K-1).
Let e∈V(L(G)), then e is for some u, v∈V(G). Since, e is an edge of G, then e is adjacent with 2(K-1) edges of G. Hence, the degree e∈ V(L(G)) is 2(K-1). Hence, the result.
Corollary 1: If G is a cycle of length n, then Q1(G) is the ring sum of exactly two disjoint cycles of length n.
Proof: Suppose G is a cycle of length n. From Mishra and Chandrasekaran (2007), we have that, if G is a cycle of length n, then L(G) is a cycle of length n. Since, Q1(G) = G⊕L(G) (by above theorem 1) Q1 (G) is equal to the ring sum of two disjoint cycles of length n. The proof is complete.
Corollary 2: For all n, Q1(Kn) is a ring sum of r-regular Kn and 2(r-1) regular LKn graph, where r denotes the degree of the vertices in complete graph Kn on n vertices.
Proof: Consider r- regular Kn, n∈N, then d(v) = r for all v∈V(Kn). We have to prove Q1(Kn) contains exactly one r-regular Kn and 2(r-1)-regular L(Kn). Since, Q1(Kn) = Kn⊕L(Kn). Clearly by hypothesis Kn is r-regular. We have to prove L(Kn) is 2(r-1) regular. Let e∈V(L(Kn)) then for some, v∈V(Kn), that implies e∈E(Kn), then e is adjacent with 2(r-1) edges of G. Hence, the degree of e∈V(L(Kn)) is 2(r-1), d(e) = 2(r-1), for all e∈V(L(Kn)). Therefore, L (Kn) is 2(r-1) regular.
Theorem 2: For any Km, n(m ≠ n) graph with the bipartition X, Y, the degree of the vertices in the X-Set is n, the degree of the vertices in Y-set is m and the remaining vertices have degree m+n-2 in Q1(Km, n) of Km, n.
Proof: Let X, Y be a partition of Km, n. X contains m vertices and Y contains n vertices. Let v∈X, then, v is adjacent with n vertices in Y. Therefore, v has degree n in Q1(Km, n). Hence, the degree of the vertices in X is n in Q1(Km, n). Similarly u∈Y then, u is adjacent with m vertices in X. Therefore, u has degree m in Q1(Km, n). Hence, the degree of every vertex in Y is m in Q1(Km, n). Let e be an edge of Km, n. Clearly e is incident with two vertices , for some, u∈X, v∈Y. Since, u is incident with n edges including e. Similarly v is incident with m edges including e. Therefore, e is adjacent with (n-1) edges through u and (m-1) edges through v. Hence, the degree of e in Q1(Km, n) is(n-1)+(m-1) = m+n-2. This completes the proof.
Example 2: The following example illustrates the Theorem 2 (Fig. 2).
Theorem 3: Let G be a graph with v>1, e≥1, then χ(Q1(G))≥2.
Fig. 2(a-b): | The Graph of (a) K1,8 (b) Q1(K1,8) |
Proof: Let e be an edge of G:
Therefore, the vertex e∈V(Q1(G)) is adjacent with vertices u and v in G.
χ(Q1(G))≥2 |
Corollary 3: The Chromatic number (Mishra and Chandrasekaran, 2007) of k1,n of Q1(k1,n) is 2.
Corollary 4: The chromatic number of line graph of Q1(k1,n) is n-1.
This study illustrates some remarkable properties of 1-quasi-total graphs. It has been obtained certain results on graphs such as regular graphs, complete graphs, complete bipartite, cycles and chromatic number of 1-quasi-total graphs. Also the above discussion investigates the concepts of 1-quasi-total graph in regular and complete graphs. Also it has been deliberated the chromatic number of 1-quasi-total graph and 1-quasi-total graph of a complete bi- partite graphs.