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
PDF
HTML XML
96
Downloads
440
Views
Citations

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

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].

Share and Cite:

Xie, G. and Li, Y. (2023) Cycle Multiplicity of Total Graph of Complete Bipartite Graph. *Open Journal of Discrete Mathematics*, **13**, 95-99. doi: 10.4236/ojdm.2023.134009.

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}* ×

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

$CM\left({K}_{n}\right)=\{\begin{array}{ll}\lfloor \frac{{n}^{2}-2n}{6}\rfloor ,\hfill & \text{If}\text{\hspace{0.17em}}n\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\text{even},\hfill \\ \lfloor \frac{{n}^{2}-2n}{6}\rfloor ,\hfill & \text{If}\text{\hspace{0.17em}}n\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\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

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

Now we prove our main result as fellow.

Lemma 1. Let *K _{n}* be a complete graph with order

$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}\text{\hspace{0.17em}}m,n\text{\hspace{0.17em}}\text{are}\text{\hspace{0.17em}}\text{both}\text{\hspace{0.17em}}\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}* ×

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}\text{\hspace{0.17em}}m,n\text{\hspace{0.17em}}\text{are}\text{\hspace{0.17em}}\text{both}\text{\hspace{0.17em}}\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}\text{\hspace{0.17em}}n\text{\hspace{0.17em}}\text{is}\text{\hspace{0.17em}}\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.

[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. |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2024 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.