Cyclic ordering of edges without long acyclic subsequences

Liang, Yanting; Locke, Sarah; Trice, Andrea

doi:10.61091/cn235-04

Abstract

References

Congressus Numerantium

Volume 235
Pages: 41-46

Research article

Cyclic ordering of edges without long acyclic subsequences

^¹, ^², ^³

¹University of Wisconsin Oshkosh, Oshkosh, WI 54901

²University of Tennessee at Martin, Martin, TN 38238

³West Virginia University, Morgantown, WV 26506

Received: 27/08/2024
Accepted: 08/01/2025
Published: 11/02/2025

Copyright Link
License

Abstract

Let $ G $ be a connected graph with $ m $ edges. The density of a nontrivial subgraph $ H $ with $ \omega(H) $ components is $ d(H) = \frac{|E(H)|}{|V(H)| – \omega(H)} $. A graph $ G $ is uniformly dense if for any nontrivial subgraph $ H $ of $ G $, $ d(H) \leq d(G) $. For each cyclic ordering $ o=(e_1, e_2, \dots, e_m) $ of $ E(G) $, let $ h(o) $ be the largest integer $ k $ such that every $ k $ cyclically consecutive elements in $ o $ induce a forest in $ G $; and the largest $ h(o) $, taken among all cyclic orderings of $ G $, is denoted by $ h(G) $. A cyclic ordering $ o $ of $ G $ is a cyclic base ordering if $ h(o) = |V(G)| – \omega(G) $. In [15], Kajitani et al. proved that every connected nontrivial graph with a cyclic base ordering is uniformly dense, and conjectured that every uniformly dense graph has a cyclic base ordering. This motivates the study of $ h(G) $. In this paper, we investigate the value of $ h $ for some families of graphs and determine all connected graphs $ G $ with $ h(G) \leq 2 $.

Keywords: uniformly dense graphs, cyclic orderings, cyclic base ordering

1. Introduction

In this paper, graphs considered are finite and loopless. We follow [1] for undefined terms and notation. A graph is nontrivial if its edge set is not empty. For a nontrivial graph $G$, let $\omega(G)$ be the number of connected components of $G$. Following the notations in [3], define the density $d(G)$ and the fractional arboricity $\gamma(G)$ as follows: \[d(G) = \frac{|E(G)|}{|V(G)| – \omega(G)} \mbox{ and } \gamma(G) = \max\{d(H):\emptyset \neq E(H) \subseteq E(G) \}.\]

A graph $G$ is uniformly dense if $\gamma(G) = d(G)$. Uniformly dense graphs have been considered as models of certain secured networks, as seen in [12]. There have been quite a few studies on uniformly dense graphs and matroids, as can be seen in [3,2,4,5,6,8,9,10,11,12,7,14,15,13,16,17,18,19], and the references therein, among others.

Let $m$ denote the number of edges of $G$. A sequence to list all the edges in $G$ is a cyclic ordering of $G$ if the subscripts of the sequence are taken modulo $m$. Let ${\mathcal{O}}(G)$ be the collection of all cyclic ordering of $G$. For each $o=(e_1, e_2, \cdots, e_m) \in {\mathcal{O}}(G)$, let $h(o)$ be the largest integer $k$ such that every $k$ cyclically consecutive elements in $o$ induces a forest in $G$, where a forest is a graph that contains no cycles; and define $h(G) = \max \{h(o): o \in {\mathcal{O}}(G)\}$. By definition, $1 \le h(G) \le |V(G)| – \omega(G)$ for any loopless nontrivial graph $G$. It is therefore of particular interests to investigate the conditions when equality holds in either the lower bound or the upper bound. A cyclic order $o \in {\mathcal{O}}(G)$ is a cyclic base ordering if $h(o) = |V(G)| – \omega(G)$. The following has been proved by Kajitani et al, relating cyclic orderings with the property of being uniformly dense in graphs.

Theorem 1.1. [15] Let $G$ be a connected nontrivial graph on $n$ vertices. If $h(G) = n-1$, then $G$ is uniformly dense.

Kajitani et al. in [15] proposed the conjecture that if $G$ is uniformly dense, then $h(G) = n-1$. Thus investigating the value of $h(G)$ is of interests. The purpose of this study is to investigate the relationship between the value of $h(G)$ and the structural properties of $G$ which may measure the closeness for a graph $G$ to being uniformly dense. In the next section, we present some preliminaries, and the main results are stated and proved in Section 3.

2. Preliminaries

Proposition 2.1. Let $G$ be a connected nontrivial graph with $n$ vertices. Then every cyclic ordering of $G$ is a cyclic base ordering if and only if $G$ is either a tree or a cycle.

Proof. We prove the sufficiency first. If $G$ is a tree, then $|E(G)|=n-1$. Clearly, for any cyclic ordering $o$ of $G$, $h(o)=h(G)=n-1$ and so it is a cyclic base ordering. Now we suppose $G$ is a cycle. We know $|E(G)|=n$ and $h(G)<n$. Notice that every set of $n-1$ edges induces a path. Therefore, for any cyclic ordering $o$ of $G$, $h(o)=n-1$ and so $h(G)=n-1$. Every cyclic ordering of $G$ is a cyclic base ordering.

We prove the necessity by contradiction. Suppose every cyclic ordering of $G$ is a cyclic base ordering but $G$ is neither a tree nor a cycle. Since $G$ is connected, $|E(G)|\geq n$ and $G$ contains a cycle $C$ but $G\neq C$. Without loss of generality, suppose $E(G)=\{e_1, e_2, \cdots, e_m\}$ and $C=e_1e_2\cdots e_ie_1$ is a cycle of $G$. Consider the cyclic ordering $o=(e_1, e_2, \cdots, e_i, e_{i+1}, \cdots, e_m)$. We have $h(o)< i\leq n-1$ because $e_1e_2\cdots e_ie_1$ is a cycle and $G\neq C$. However, by the assumption, it is a cyclic base ordering of $G$, so $h(o)=n-1$, a contradiction. This completes the proof. ◻

Suppose $u,v\in V(G)$. Let $E_{uv}=\{e\in E(G)|~\mbox{$e$ is incident with both $u$ and $v$}\}$, and $m_{uv}=|E_{uv}|$. If there is no edge between $u$ and $v$, then $E_{uv}=\emptyset$ and $m_{uv}=0$. Let $\Delta_m(G)=\max\{m_{uv}|u,v\in V(G)\}$. We prove the following.

Lemma 2.2. For every graph $G$, if $|E(G)| <(i+1)\Delta_m(G)$, then $h(G)\le i$ where $i\ge 1$.

Proof. Assume that $h(G)\ge i+1$. Suppose $|E_{uv}|=\Delta_m(G)$ where $u,v\in V(G)$. Then for any cyclic ordering, every $i+1$ cyclically consecutive elements induce a forest in $G$, and contain at most one edge in $E_{uv}$. Then $m\ge (i+1)\Delta_m(G)$. It contradicts to $m<(i+1)\Delta_m(G)$. Hence $h(G)\le i$. ◻

Corollary 2.3. For a nontrivial graph $G$, $m<2\Delta_m(G)$ if and only if $h(G)=1$.

Proof. We prove the necessity first. It is known that $h(G)\ge 1$. By Lemma 2.2, $h(G)\leq1$. Therefore, $h(G)=1$. It remains to prove the sufficiency. Assume that $m\ge 2\Delta_m(G)$. Suppose $E_{uv}=\{e_1, \cdots, e_{\Delta_m(G)}\}$, where $u,v\in V(G)$. Since $m\ge 2\Delta_m(G)$ and $|E_{uv}|=\Delta_m(G)$, we can put at least one edge after $e_i$ and the edges between $e_i$ and $e_{i+1}$ are different for $1\le i\le \Delta_m(G)$ and $e_{\Delta_m(G)+1}=e_1$. Then we have a cyclic ordering $o$ such that $h(o)\ge 2$. It is a contradiction to $h(G)=1$. Thus $m<2\Delta_m(G)$. ◻

3. Results

In this section, we study $h(G)$ of the complete graph on three vertices, denoted by $K_3$, where multiple edges are allowed. Also, we prove a formula for obtaining $h(G)$ under a particular set of constraints. Finally, we propose the structure for all graphs with $h(G) \leq 2$ and prove the necessity of the conjecture.

Theorem 3.1. Let $G$ be the graph $(m_1,m_2,m_3)K_3$ where $m_1,m_2,m_3$ are the number of edges between two vertices and $m_1 \leq m_2 \leq m_3$. Then \[h((m_1,m_2,m_3)K_3)=\left\{ \begin{array}{lr} 1, & \mbox{if}~ m_3 > m_1 + m_2 \\ 2, & \mbox{if}~ m_3 \leq m_1 + m_2 \\ \end{array} \right. \tag{1}\]

Proof. Let $V(G)=\{v_1,v_2,v_3\}$, $E_i$ be the set of all edges with endpoints $v_i$ and $v_{i+1}$ for $1\leq i\leq 2$, $E_3$ be the set of all edges with endpoints $v_3$ and $v_1$, and $m_i=|E_i|$ for $i \in \{1,2,3\}$. Then $m_3=\Delta_m(G)$.

If $m_3 > m_1 + m_2$, then $m=m_1+m_2+m_3<2m_3=2\Delta_m(G)$. By Corollary 2.3, $h(G)=1$. Now suppose $m_3 \leq m_1 + m_2$. Let $E_i=\{e_1^i,e_2^i, …, e_{m_i}^i\}$. Then there exists a cyclic ordering $o$ such that the ordering alternates between an edge from $E_3$ and an edge from $E_1$ or $E_2$. Since $m_3 \leq m_1 + m_2$, there are at least as many edges in $E_1 \cup E_2$ as in $E_3$. So $h(G) \geq 2$. Notice that $h(G) \leq |V(G)|-1=2$. Therefore, $h(G)=2$. ◻

Let $S_G$ be the graph obtained from $G$ by combining all multiple edges between two vertices to only one edge. Let $g(S_G)$ be the girth of $S_G$, which is the length of the shortest cycle in $S_G$. See Figure 1 for an example. If $S_G$ is a tree, we define $g(S_G)=\infty$.

Theorem 3.2. For a graph $G$, suppose $g(S_G) \geq i+1$. Then each of the following holds.

(i) If $i\Delta_m(G) \leq m$, then $h(G)\geq i$.

(ii) If $m \leq (i+1) \Delta_m(G) -1$, then $h(G)\leq i$.

Proof. Let $E(S_G)=\{e_1, e_2, \cdots, e_t\}$, $E_i$ be the set of all edges in $G$ that were combined to $e_i$ in $S_G$ and $E_i=\{e_1^i,e_2^i, …, e_{m_i}^i\}$ where $m_i=|E_i|$ for $1\leq i\leq t$. Without loss of generality, we suppose $\Delta_m(G)=m_1\geq m_2\geq \cdots\geq m_t$. For each cyclic ordering of $G$, $(e^1_{j_1}, \cdots, e^1_{j_2}, \cdots, e^1_{j_{\Delta_m(G)}}, \cdots)$ where $\{j_1, j_2, \cdots, j_{\Delta_m(G)}\}=\{1, 2, \cdots, \Delta_m(G)\}$, the edges $\{e^1_{j_1}, e^1_{j_2}, \cdots, e^1_{j_{\Delta_m(G)}}\}$ in $E_1$ divide the ordering into $\Delta_m(G)$ intervals with the first edges from $E_1$.

If $m\geq i\Delta_m(G)$, since $g(S_G) \geq i+1$, there is a cyclic ordering $o$ such that each interval has at least $i$ edges and no multiple edges from the same $E_i$ are in the same interval for $1\leq i\leq t$. So $h(G)\geq h(o)\geq i$. This proves part $(i)$.

Suppose $m \leq (i+1) \Delta_m(G) -1$. To prove by contradiction, assume that $G$ has a cyclic order $o$ with $h(o) \geq i+1$. The edges in $E_1$ divide the ordering into $\Delta_m(G)$ intervals. If one such interval has at most $i$ edges, then length of this interval together with the edges from $E_1$ on both sides of the interval is at most $1+(i-1)+1=i+1$ and it contains a 2-cycle, contrary to $h(o)\geq i+1$. Hence, every interval must have at least $i+1$ edges. So $m \geq \Delta_m(G)(i+1)$. ◻

Suppose $g(S_G)=3$. Let $\Delta_\Delta=\max\{\lceil\frac{m_1+m_2+m_3}{2}\rceil \; | \; (m_1,m_2,m_3)K_3$ is a subgraph of $G\}$. If $g(S_G)>3$, we define $\Delta_\Delta=0$. Let $\ell=m-m_1-m_2-m_3$.

We propose a structure for all graphs that satisfy $h(G)=2$ and prove the necessity. Below, we use $\Delta_m$ for $\Delta_m(G)$.

Conjecture 3.3. Let $G$ be a connected graph. Then \[\left\{ \begin{array}{ll} 2\Delta_m\le m\le 3\Delta_m-1, & if~\Delta_\Delta\le \Delta_m\\ \ell<\Delta_\Delta, & if~\Delta_\Delta>\Delta_m \end{array}\right.\] if and only if $h(G)=2$.

Theorem 3.4.

Let $G$ be a connected graph. If \[\left\{ \begin{array}{ll} 2\Delta_m\le m\le 3\Delta_m-1, & if~\Delta_\Delta\le \Delta_m\\ \ell<\Delta_\Delta, & if~\Delta_\Delta>\Delta_m \end{array}\right.\] then $h(G)=2$.

Proof. If $g(S_G)> 3$, then $G$ has no 3-cycle and $\Delta_\Delta=0\leq \Delta_m(G)$. If $2\Delta_m\le m\le 3\Delta_m-1$, by Theorem 3.2, $h(G)=2$.

It is sufficient to prove the case when $g(S_G)=3$. If $\Delta_\Delta\le \Delta_m$, then $2\Delta_m\le m\le 3\Delta_m-1$. By Lemma 2.2, $h(G)\le 2$. And by Corollary 2.3, $h(G)\neq 1$. Therefore, $h(G)=2$. If $\Delta_\Delta>\Delta_m$, suppose $(m_1,m_2,m_3)K_3$ satisfies $\Delta_\Delta$. Since $\Delta_\Delta>\Delta_m$, $m\ge m_1+m_2+m_3\geq 2\Delta_\Delta -1$ by the definition of $\Delta_\Delta$. Therefore, $m> 2\Delta_m-1$, i.e. $m\ge 2\Delta_m$. By Corollary 2.3, $h(G)\ge 2$. Assume that $h(G)\ge 3$. Let $o$ be the cyclic ordering such that $h(o)\ge 3$. Then every $3$ cyclically consecutive elements in $o$ has at most two edges in $(m_1,m_2,m_3)K_3$. Then $\ell\ge \frac{m_1+m_2+m_3}{2}$, so $\ell\geq \Delta_\Delta$. It contradicts to $\ell<\Delta_\Delta$. Thus $h(G)=2$. ◻

Acknowledgements

We would like to express our sincere gratitude to Dr. Hong-Jian Lai for his introducing the concept of $h(G)$ and proposing the research problems.

Declarations

The authors declare no conflict of interest.

References:

J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 2008.
P. A. Catlin, J. W. Grossman, and A. M. Hobbs. Graphs with uniform density. Congressus Numerantium, 65:281–286, 1988.
P. A. Catlin, J. W. Grossman, A. M. Hobbs, and H.-J. Lai. Fractional arboricity, strength, and principal partition in graphs and matroids. Discrete Applied Mathematics, 40:285–302, 1992.
C. C. Chen, K. M. Koh, and Y. H. Peng. On the higher-order edge toughness of a graph. Discrete Mathematics, 111:113–123, 1993. https://doi.org/10.1016/0012-365X(93)90147-L.
Z.-H. Chen and H.-J. Lai. The higher-order edge toughness of a graph and truncated uniformly dense matroids. Journal of Combinatorial Mathematics and Combinatorial Computing, 22:157–160, 1996.
R. Cordovil and M. L. Moreira. Base-cobase graphs and polytopes of matroids. Combinatorica, 13:157–165, 1993.
J. v. den Heuvel and S. Thomasse. Cyclic ordering of matroids. Journal of Combinatorial Theory, Series B, 102:638–646, 2012.
R. Godorvil and M. L. Moreira. Base-cobase graphs and polytopes of matroids. Combinatorica, 13:157–165, 1993.
D. Goncalves. Étude de différents problèmes de partitions de graphes. PhD thesis, Université de Bordeaux I, 2006. Received May 6, 2007.
X. Gu, K. Horacek, and H.-J. Lai. Cyclic base orderings in some classes of graphs. Journal of Combinatorial Theory and Combinatorial Computing, 88:39–50, 2014.
A. M. Hobbs. Computing edge-toughness and fractional arboricity. Contemporary Mathematics, 89:89–106, 1989.
A. M. Hobbs. Survivability of networks under attack. In J. G. Michaels and K. H. Rosen, editors, Applications of Discrete Mathematics, pages 332–353, 1991.
L. Kamuan, A. M. Hobbs, and H. Y. Lai. Transforming a graph into a 1-balanced graph. Discrete Applied Mathematics, 157:300–308, 2009. https://doi.org/10.1016/j.dam.2008.03.012.
Y. Kazitani and K. Sugishita. Ordering of elements of a matroid such that its consecutive r elements are independent. In Proceedings of the Technical Group Circuits and Systems, Institute of Electrical and Communications Engineering of Japan, pages 89–94, 1983. CAS830124.
Y. Kazitani, S. Ueno, and H. Miyano. Ordering the elements of a matroid such that its consecutive w elements are independent. Discrete Mathematics, 72:187–194, 1988. https://doi.org/10.1016/0012-365X(88)90209-9.
H.-J. Lai and H. Y. Lai. A note on uniformly dense matroids. Utilitas Mathematica, 40:251–256, 1991.
H.-J. Lai and H. Y. Lai. Every matroid is a submatroid of a uniformly dense matroid. Discrete Applied Mathematics, 63:151–160, 1995. https://doi.org/10.1016/0166-218X(94)00029-D.
H. Narayanan and N. Vartak. An elementary approach to the principal partition of a matroid. Transactions of the Institute of Electrical and Electronics Engineers Japan, E64:227–234, 1981.
N. Tomizawa. Strongly irreducible matroids and principal partition of a matroid into strongly irreducible minors. Electronics and Communications in Japan, 59A(2):1–10, 1976.

[1] J. A. Bondy and U. S. R. Murty. Graph Theory. Springer, 2008.

[2] P. A. Catlin, J. W. Grossman, and A. M. Hobbs. Graphs with uniform density. Congressus Numerantium, 65:281–286, 1988.

[3] P. A. Catlin, J. W. Grossman, A. M. Hobbs, and H.-J. Lai. Fractional arboricity, strength, and principal partition in graphs and matroids. Discrete Applied Mathematics, 40:285–302, 1992.

[4] C. C. Chen, K. M. Koh, and Y. H. Peng. On the higher-order edge toughness of a graph. Discrete Mathematics, 111:113–123, 1993. https://doi.org/10.1016/0012-365X(93)90147-L.

[5] Z.-H. Chen and H.-J. Lai. The higher-order edge toughness of a graph and truncated uniformly dense matroids. Journal of Combinatorial Mathematics and Combinatorial Computing, 22:157–160, 1996.

[6] R. Cordovil and M. L. Moreira. Base-cobase graphs and polytopes of matroids. Combinatorica, 13:157–165, 1993.

[7] J. v. den Heuvel and S. Thomasse. Cyclic ordering of matroids. Journal of Combinatorial Theory, Series B, 102:638–646, 2012.

[8] R. Godorvil and M. L. Moreira. Base-cobase graphs and polytopes of matroids. Combinatorica, 13:157–165, 1993.

[9] D. Goncalves. Étude de différents problèmes de partitions de graphes. PhD thesis, Université de Bordeaux I, 2006. Received May 6, 2007.

[10] X. Gu, K. Horacek, and H.-J. Lai. Cyclic base orderings in some classes of graphs. Journal of Combinatorial Theory and Combinatorial Computing, 88:39–50, 2014.

[11] A. M. Hobbs. Computing edge-toughness and fractional arboricity. Contemporary Mathematics, 89:89–106, 1989.

[12] A. M. Hobbs. Survivability of networks under attack. In J. G. Michaels and K. H. Rosen, editors, Applications of Discrete Mathematics, pages 332–353, 1991.

[13] L. Kamuan, A. M. Hobbs, and H. Y. Lai. Transforming a graph into a 1-balanced graph. Discrete Applied Mathematics, 157:300–308, 2009. https://doi.org/10.1016/j.dam.2008.03.012.

[14] Y. Kazitani and K. Sugishita. Ordering of elements of a matroid such that its consecutive r elements are independent. In Proceedings of the Technical Group Circuits and Systems, Institute of Electrical and Communications Engineering of Japan, pages 89–94, 1983. CAS830124.

[15] Y. Kazitani, S. Ueno, and H. Miyano. Ordering the elements of a matroid such that its consecutive w elements are independent. Discrete Mathematics, 72:187–194, 1988. https://doi.org/10.1016/0012-365X(88)90209-9.

[16] H.-J. Lai and H. Y. Lai. A note on uniformly dense matroids. Utilitas Mathematica, 40:251–256, 1991.

[17] H.-J. Lai and H. Y. Lai. Every matroid is a submatroid of a uniformly dense matroid. Discrete Applied Mathematics, 63:151–160, 1995. https://doi.org/10.1016/0166-218X(94)00029-D.

[18] H. Narayanan and N. Vartak. An elementary approach to the principal partition of a matroid. Transactions of the Institute of Electrical and Electronics Engineers Japan, E64:227–234, 1981.

[19] N. Tomizawa. Strongly irreducible matroids and principal partition of a matroid into strongly irreducible minors. Electronics and Communications in Japan, 59A(2):1–10, 1976.

Contents

Congressus Numerantium

Cyclic ordering of edges without long acyclic subsequences

Abstract

1. Introduction

2. Preliminaries

3. Results

Acknowledgements

Declarations

References:

Information

Guidelines

CP Initiatives

Follow CP