Cycle Multiplicity of Total Graph of Complete Bipartite Graph

Ganghua Xie, Yinkui Li

Department of Mathematics, Qinghai Nationalities University, Xining, China.

DOI: 10.4236/ojdm.2023.134009                

Abstract

Cycle multiplicity of a graph G is the maximum number of edge disjoint cycles in G. In this paper, we determine the cycle multiplicity of and then obtain the formula of cycle multiplicity of total graph of complete bipartite graph, this generalizes the result for, which is given by M.M. Akbar Ali in [1].

Keywords

Cycle Multiplicity, Complete Bipartite Graph, Total Graph

1. Introduction

The cycle multiplicity is the maximum number of line disjoint subgraphs contained in G so that each subgraph is not acyclic. This number is called the cycle multiplicity of G denoted by $CM\left(G\right)$ . The formula for cycle multiplicity of complete and complete bipartite graph is given in [2] . In [3] , authors found an upper bound for the line and middle graph of any graph. Also they obtained the formula for line and total graph of any forest. Recently, M.M. Akbar Ali and S.P Anayappan discuss cycle multiplicity of total graph of $K_{1,n}$ in [1] . In [4] , Li Yinkui determines the cycle multiplicity of some Cartesian product graphs. In [5] , Song’s result improves the theorem of Ma and Yan by optimizing the lower bound of $\left|V\left(G\right)\right|$ .

Let $G_1,G_2,\cdots ,G_n$ be connected graps, the Cartesian product $G_1\times G_2\times \cdots \times G_n$ is a graph which has vertex set $V\left(G_1\right)\times V\left(G_2\right)\times \cdots \times V\left(G_n\right)$ with two vertices $u=\left(u_1,u_2,\cdots ,u_n\right)$ and $v=\left(v_1,v_2,\cdots ,v_n\right)$ adjacent if for exactly one i, $u_i\ne v_i$ and $\left(u_i,v_i\right)$ is an edge in $G_i$ . The total graph $T\left(G\right)$ of G is a such graph that the vertex set of $T\left(G\right)$ is $V\left(G\right)\cup E\left(G\right)$ and two vertices $x,y$ in the vertex set of $T\left(G\right)$ are adjacent in $T\left(G\right)$ in case one of the following holds: 1) $x,y$ are in $V\left(G\right)$ and x is adjacent to y in G. 2) $x,y$ are in $E\left(G\right)$ and $x,y$ are adjacent in G. 3) x is in $V\left(G\right)$ , y is in $E\left(G\right)$ , and $x,y$ are incident in G.

As we all know that Cartesian product graphs and total graphs play important role in research of Graph Theory and Networks. In this paper, we determine the cycle multiplicity of Cartesian product graph $K_m\times K_n$ and then get the formula of cycle multiplicity for total graph of $K_{m,n}$ .

Through this paper, we consider finite, simple, undirected graph. For any real number r, $\lceil r\rceil$ and $\lfloor r\rfloor$ denote the largest integer not exceeding r and the least integer not less than r, respectively. The other notations and terminology can be found in [6] .

2. Cycle Multiplicity of K_m × K_n

In this section, we determine the cycle multiplicity of $K_m\times K_n$ . First we give some useful Lemmas.

Lemma 1. [2] Let K_n is a complete graph with order n. Then the cycle multiplicity of K_n is

$CM\left(K_n\right)=\{\begin{array}{ll}\lfloor \frac{n^2-2n}{6}\rfloor ,\hfill & \text{If}n\text{is}\text{even},\hfill \\ \lfloor \frac{n^2-2n}{6}\rfloor ,\hfill & \text{If}n\text{is}\text{odd}.\hfill \end{array}$

Lemma 2. Let $V\left(K_n\right)=\left\{u_1,u_2,\cdots ,u_n\right\}$ be the vertex set of complete graph K_n. Suppose $C^{\ast }$ is a maximum cycle set of K_n. Then

1) If $n\equiv 1,3\left(\mathrm{mod}6\right)$ , $C^{\ast }=\lfloor \frac{n^2-n}{6}\rfloor C_3$ with no free edges;

2) If $n\equiv 5\left(\mathrm{mod}6\right)$ , $C^{\ast }=C_4\cup \left(\lfloor \frac{n^2-n}{6}\rfloor -1\right)C_3$ with no free edges;

3) If $n\equiv 0,2\left(\mathrm{mod}6\right)$ , $C^{\ast }=\lfloor \frac{n^2-2n}{6}\rfloor C_3$ with $\frac{n}{2}$ free edges $u_i{u}_{i+\frac{n}{2}}$ for $1\le i\le \frac{n}{2}$ ;

4) If $n\equiv 4\left(\mathrm{mod}6\right)$ , $C^{\ast }=C_4\cup \left(\lfloor \frac{n^2-2n}{6}\rfloor -1\right)C_3$ with $\frac{n}{2}$ free edges $u_i{u}_{i+\frac{n}{2}}$ for $1\le i\le \frac{n}{2}$ .

Proof: If n is odd. By Lemma 2.1, we know that $\left|C^{\ast }\right|=\lfloor \frac{n^2-n}{6}\rfloor$ . If $n\equiv 1,3\left(\mathrm{mod}6\right)$ , $C^{\ast }=\lfloor \frac{n^2-n}{6}\rfloor C_3$ with no free edge since $3\lfloor \frac{n^2-n}{6}\rfloor =\frac{n\left(n-1\right)}{2}$ , thus (1) hold. If $n\equiv 5\left(\mathrm{mod}6\right)$ , $C^{\ast }=C_4\cup \left(\lfloor \frac{n^2-n}{6}\rfloor -1\right)C_3$ with no free edge since $3\lfloor \frac{n^2-n}{6}\rfloor =\frac{n\left(n-1\right)}{2}-1$ , this means (2) hold.

If n is even. Since every vertex $u_i\in V\left(K_n\right)$ has odd degree and is incident with at least one edge not belong to any cycle in $C^{\ast }$ . By the maximality of $C^{\ast }$ ,

we know that the free edges of $C^{\ast }$ are just diagonal edges of K_n such as $u_i{u}_{i+\frac{n}{2}}$ for $1\le i\le \frac{n}{2}$ . Thus the number of edges of $C^{\ast }$ is not more than $\frac{n\left(n-2\right)}{2}$ . Combine this with $\left|C^{\ast }\right|=\lfloor \frac{n^2-2n}{6}\rfloor$ , (3) and (4) are hold where n is even.

Now we prove our main result as fellow.

Lemma 1. Let K_n be a complete graph with order n. Then

$CM\left(K_n\right)=\{\begin{array}{ll}m\lfloor \frac{n\left(n-2\right)}{6}\rfloor +\lfloor \frac{m\left(m-2\right)}{6}\rfloor +\frac{mn}{4},\hfill & \text{If}m,n\text{are}\text{both}\text{even},\hfill \\ mCM\left(K_n\right)+nCM\left(K_m\right),\hfill & \text{otherwise}.\hfill \end{array}$

Proof: Denote $K_m\times K_n$ by G and vertex $\left(u_i,v_j\right)$ by $w_{ij}$ for $u_i\in V\left(K_m\right)$ , $v_j\in V\left(K_n\right)$ , $1\le i\le m$ , $1\le j\le n$ . By $K_m^j$ and $K_n^j$ we denote subgraphs induced by $\left\{w_{ij}|1\le i\le m\right\}$ and $\left\{w_{ij}|1\le j\le n\right\}$ , respectively. It is clear that $K_m^j\cong K_m$ and $K_n^i\cong K_n$ . So both of $n{K}_m$ and $m{K}_n$ are spanning subgraphs of G. Now we distinguish two cases to complete the proof.

Case 1: Both of m, n are even.

Since the $n{K}_m$ and the $m{K}_n$ are two classes edge disjoint spanning subgraphs of G, there are at most $mCM\left(K_n\right)+nCM\left(K_m\right)$ edge disjoint cycles in $n{K}_m\cup m{K}_n$ , denoted this cycle set by $C^{\ast }$ . By Lemma 2.2, we know that $C^{\ast }$ is consisted of 3-cycles and 4-cycles, and there will be mn free edges respect to $C^{\ast }$ , such as $w_{ij}{w}_{\left(i+\frac{m}{2}\right)j}$ in every $K_m^j$ and $w_{ij}{w}_{i\left(j+\frac{n}{2}\right)}$ in every $K_n^i$ .

Follow this procedure, we expand cycle set $C^{\ast }$ by using mn free edges. Since all free edges are diagonal edges of $K_m^j$ and $K_n^i$ , the shortest cycle we can form by using free edges is 4-cycle. This implies that we get at most $\frac{mn}{4}$ edge disjoint 4-cycles. Thus the total number of edge disjoint cycles in G is at most $mCM\left(K_n\right)+nCM\left(K_m\right)+\frac{mn}{4}$ . Combine this with Lemma 2.1, we get $CM\left(G\right)\le m\lfloor \frac{n\left(n-2\right)}{6}\rfloor +n\lfloor \frac{m\left(m-2\right)}{6}\rfloor +\frac{mn}{4}$ .

On the other hand, because the $n{K}_m$ and the $m{K}_n$ are edge disjoint spanning subgraphs of G, we can find $mCM\left(K_n\right)+nCM\left(K_m\right)$ edge disjoint cycles in G, denote this cycle set as $C^{\ast }$ . By Lemma 2.2, there are mn free edges respect

to $C^{\ast }$ . Using these free edges can form $\frac{mn}{4}$ edge disjoint 4-cycles such as $w_{ij}{w}_{\left(i+\frac{m}{2}\right)j}{w}_{\left(i+\frac{m}{2}\right)\left(j+\frac{n}{2}\right)}{w}_{i\left(j+\frac{n}{2}\right)}$ , $1\le i\le \frac{m}{2}$ , $1\le j\le \frac{n}{2}$ . By the definition of cycle multiplicity and Lemma 2.1, we have $CM\left(G\right)\ge mCM\left(K_n\right)+nCM\left(K_m\right)+\frac{mn}{4}=m\lfloor \frac{n\left(n-2\right)}{6}\rfloor +n\lfloor \frac{m\left(m-2\right)}{6}\rfloor +\frac{mn}{4}$ .

Therefore, $CM\left(G\right)=m\lfloor \frac{n\left(n-2\right)}{6}\rfloor +n\lfloor \frac{m\left(m-2\right)}{6}\rfloor +\frac{mn}{4}$ when both of m, n are even.

3. Cycle Multiplicity of Total Graph of Complete Bipartite Graph K_m × K_n

Theorem 2. Let $T\left(G\right)$ be a total graph of graph G. Then cycle multiplicity of $T\left(G\right)$ is $CM\left(T\left(G\right)\right)=\left|E\left(G\right)\right|+CM\left(L\left(G\right)\right)$ , where $L\left(G\right)$ is line graph of G.

Proof. For convenience narrate we denote $E\left(G\right)=V\left(L\left(G\right)\right)=\left\{e_1,e_2,\cdots ,e_m\right\}$ such that $e_i=v_j{v}_k$ for $v_j,v_k\in V\left(G\right)=\left\{v_1,v_2,\cdots ,v_n\right\}$ . By the definition of total graph we know that graph G and its line graph $L\left(G\right)$ are both subgraphs of total graph $T\left(G\right)$ and no vertex of $T\left(G\right)$ having thus edges of both G and $L\left(G\right)$ incident to it. Hence the line set of $T\left(G\right)$ may be partitioned into three sets and we call an edge of $T\left(G\right)$ a G-edge, L-edge, or I-edge according to its belong to G, to $L\left(G\right)$ , or to neither G nor $L\left(G\right)$ , respectively. Now to each G-edge we may obviously associate two I-edge, which altogether form a distinct triangle such as $v_j{e}_i{v}_k$ . Thus we can obtain $\left|E\left(G\right)\right|$ edge disjoint triangles by using G-edge and I-edge. Next we consider to use L-edge to form line disjoint cycles. Clearly the edge induced subgraph of $T\left(G\right)$ by L-edge is line graph $L\left(G\right)$ of graph G, so we get $CM\left(T\left(G\right)\right)$ is more than $\left|E\left(G\right)\right|$ add the number of line disjoint cycle in $L\left(G\right)$ .

On the other hand, since any 3-cycle in $T\left(G\right)$ not exclusively formed by L-edge has only two I-edges and one G-edge. Hence the up bound for $CM\left(T\left(G\right)\right)$ may be obtained by adding the maximum number of line disjoint cycles formed exclusively with L-edges. As, by $\left|I\right|=2\left|E\left(G\right)\right|$ , We can obtain that $CM\left(T\left(G\right)\right)$ is less than or equal to the sum of $\left|E\left(G\right)\right|$ and $CM\left(L\left(G\right)\right)$ , where CM(L(G)) is the maximum number of line disjoint cycles in $L\left(G\right)$ . Thus we have $CM\left(T\left(G\right)\right)=\left|E\left(G\right)\right|+CM\left(L\left(G\right)\right)$ .

By Theorem 2.1 and 3.1 we immediately get the cycle multiplicity of $T\left(K_{m,n}\right)$ .

Corollary 3. Let $T\left(K_{m,n}\right)$ be the total graph of complete bipartite graph $K_{m,n}$ . Then cycle multiplicity of $T\left(K_{m,n}\right)$ is

$CM\left(T\left(K_{m,n}\right)\right)=\{\begin{array}{ll}\lfloor m\frac{n\left(n-2\right)}{6}\rfloor +n\lfloor \frac{m\left(m-2\right)}{6}\rfloor +\frac{5mn}{4},\hfill & \text{If}m,n\text{are}\text{both}\text{even},\hfill \\ mn+mCM\left(K_n\right)+nCM\left(K_m\right),\hfill & \text{otherwise}.\hfill \end{array}$

Corollary 4. Let $T\left(K_{m,n}\right)$ be the total graph of complete bipartite graph $K_{1,n}$ . Then cycle multiplicity of $T\left(K_{1,n}\right)$ is

$CM\left(T\left(K_{1,n}\right)\right)=n+CM\left(K_n\right)=\{\begin{array}{ll}\lfloor \frac{n^2+4n}{6}\rfloor ,\hfill & \text{If}n\text{is}\text{even},\hfill \\ \lfloor \frac{n^2+5n}{6}\rfloor ,\hfill & \text{otherwise}\hfill \end{array}$

Acknowledgements

The authors would like to thank anonymous reviewers for their valuable comments and suggests to improve the quality of the article. This work supported by QHFRP No. 2022-ZJ-753.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Akbar Ali, M.M. and Panayappan, S. (2010) Cycle Multiplicity of Total Graph of Cn, Pn, and K1,n. International Journal of Engineering, Science and Technology, 2, 54-58. https://doi.org/10.4314/ijest.v2i2.59138
[2]	Chatrand, G., Geller, D. and Hedetniemi, S. (1971) Graphs with Forbidden Subgraphs. Journal of Combinatorial Theory, 10, 12-41. https://doi.org/10.1016/0095-8956(71)90065-7
[3]	Simoes Pereira, J.M.S. (1972) A Note of Cycle Multiplicity of Line Graphs and Total Graphs. Journal of Combinatorial Theory, 12, 194-200. https://doi.org/10.1016/0095-8956(72)90024-X
[4]	Li, Y.K. (2017) Cycle Multiplicity of Some Total Graphs. Applied Mathematics and Computation, 292, 107-113. https://doi.org/10.1016/j.amc.2016.06.042
[5]	Song, C.J., Wang, Y. and Yan, J. (2023) Disjoint Cycles and Degree Sum Condition in a Graph. Journal of the Operations Research Society of China, 1-16. https://doi.org/10.1007/s40305-023-00473-5
[6]	Bondy, J.A. and Murty, U.S.R. (1976) Graph Theory with Applications. Macmillan, London.