Cyclic ordering of edges without long acyclic subsequences

Yanting Liang1, Sarah Locke2, Andrea Trice3
1University of Wisconsin Oshkosh, Oshkosh, WI 54901
2University of Tennessee at Martin, Martin, TN 38238
3West Virginia University, Morgantown, WV 26506

Abstract

Let G be a connected graph with m edges. The density of a nontrivial subgraph H with ω(H) components is d(H)=|E(H)||V(H)|ω(H). A graph G is uniformly dense if for any nontrivial subgraph H of G, d(H)d(G). For each cyclic ordering o=(e1,e2,,em) 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)|ω(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)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 ω(G) be the number of connected components of G. Following the notations in [3], define the density d(G) and the fractional arboricity γ(G) as follows: d(G)=|E(G)||V(G)|ω(G) and γ(G)=max{d(H):E(H)E(G)}.

A graph G is uniformly dense if γ(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 O(G) be the collection of all cyclic ordering of G. For each o=(e1,e2,,em)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):oO(G)}. By definition, 1h(G)|V(G)|ω(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 oO(G) is a cyclic base ordering if h(o)=|V(G)|ω(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)=n1, then G is uniformly dense.

Kajitani et al. in [15] proposed the conjecture that if G is uniformly dense, then h(G)=n1. 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)|=n1. Clearly, for any cyclic ordering o of G, h(o)=h(G)=n1 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 n1 edges induces a path. Therefore, for any cyclic ordering o of G, h(o)=n1 and so h(G)=n1. 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)|n and G contains a cycle C but GC. Without loss of generality, suppose E(G)={e1,e2,,em} and C=e1e2eie1 is a cycle of G. Consider the cyclic ordering o=(e1,e2,,ei,ei+1,,em). We have h(o)<in1 because e1e2eie1 is a cycle and GC. However, by the assumption, it is a cyclic base ordering of G, so h(o)=n1, a contradiction. This completes the proof. ◻

Suppose u,vV(G). Let Euv={eE(G)| e is incident withboth u and v}, and muv=|Euv|. If there is no edge between u and v, then Euv= and muv=0. Let Δm(G)=max{muv|u,vV(G)}. We prove the following.

Lemma 2.2. For every graph G, if |E(G)|<(i+1)Δm(G), then h(G)i where i1.

Proof. Assume that h(G)i+1. Suppose |Euv|=Δm(G) where u,vV(G). Then for any cyclic ordering, every i+1 cyclically consecutive elements induce a forest in G, and contain at most one edge in Euv. Then m(i+1)Δm(G). It contradicts to m<(i+1)Δm(G). Hence h(G)i◻

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

Proof. We prove the necessity first. It is known that h(G)1. By Lemma 2.2, h(G)1. Therefore, h(G)=1. It remains to prove the sufficiency. Assume that m2Δm(G). Suppose Euv={e1,,eΔm(G)}, where u,vV(G). Since m2Δm(G) and |Euv|=Δm(G), we can put at least one edge after ei and the edges between ei and ei+1 are different for 1iΔm(G) and eΔm(G)+1=e1. Then we have a cyclic ordering o such that h(o)2. It is a contradiction to h(G)=1. Thus m<2Δm(G)◻

3. Results

In this section, we study h(G) of the complete graph on three vertices, denoted by K3, 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)2 and prove the necessity of the conjecture.

Theorem 3.1. Let G be the graph (m1,m2,m3)K3 where m1,m2,m3 are the number of edges between two vertices and m1m2m3. Then (1)h((m1,m2,m3)K3)={1,if m3>m1+m22,if m3m1+m2

Proof. Let V(G)={v1,v2,v3}, Ei be the set of all edges with endpoints vi and vi+1 for 1i2, E3 be the set of all edges with endpoints v3 and v1, and mi=|Ei| for i{1,2,3}. Then m3=Δm(G).

If m3>m1+m2, then m=m1+m2+m3<2m3=2Δm(G). By Corollary 2.3, h(G)=1. Now suppose m3m1+m2. Let Ei={e1i,e2i,,emii}. Then there exists a cyclic ordering o such that the ordering alternates between an edge from E3 and an edge from E1 or E2. Since m3m1+m2, there are at least as many edges in E1E2 as in E3. So h(G)2. Notice that h(G)|V(G)|1=2. Therefore, h(G)=2◻

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

Figure 1 G and SG where g(SG)=3
Theorem 3.2. For a graph G, suppose g(SG)i+1. Then each of the following holds.

(i) If iΔm(G)m, then h(G)i.

(ii) If m(i+1)Δm(G)1, then h(G)i.

Proof. Let E(SG)={e1,e2,,et}, Ei be the set of all edges in G that were combined to ei in SG and Ei={e1i,e2i,,emii} where mi=|Ei| for 1it. Without loss of generality, we suppose Δm(G)=m1m2mt. For each cyclic ordering of G, (ej11,,ej21,,ejΔm(G)1,) where {j1,j2,,jΔm(G)}={1,2,,Δm(G)}, the edges {ej11,ej21,,ejΔm(G)1} in E1 divide the ordering into Δm(G) intervals with the first edges from E1.

If miΔm(G), since g(SG)i+1, there is a cyclic ordering o such that each interval has at least i edges and no multiple edges from the same Ei are in the same interval for 1it. So h(G)h(o)i. This proves part (i).

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

Suppose g(SG)=3. Let ΔΔ=max{m1+m2+m32|(m1,m2,m3)K3 is a subgraph of G}. If g(SG)>3, we define ΔΔ=0. Let =mm1m2m3.

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

Conjecture 3.3. Let G be a connected graph. Then {2Δmm3Δm1,if ΔΔΔm<ΔΔ,if ΔΔ>Δm if and only if h(G)=2.
Theorem 3.4.

Let G be a connected graph. If {2Δmm3Δm1,if ΔΔΔm<ΔΔ,if ΔΔ>Δm then h(G)=2.

Proof. If g(SG)>3, then G has no 3-cycle and ΔΔ=0Δm(G). If 2Δmm3Δm1, by Theorem 3.2, h(G)=2.

It is sufficient to prove the case when g(SG)=3. If ΔΔΔm, then 2Δmm3Δm1. By Lemma 2.2, h(G)2. And by Corollary 2.3, h(G)1. Therefore, h(G)=2. If ΔΔ>Δm, suppose (m1,m2,m3)K3 satisfies ΔΔ. Since ΔΔ>Δm, mm1+m2+m32ΔΔ1 by the definition of ΔΔ. Therefore, m>2Δm1, i.e. m2Δm. By Corollary 2.3, h(G)2. Assume that h(G)3. Let o be the cyclic ordering such that h(o)3. Then every 3 cyclically consecutive elements in o has at most two edges in (m1,m2,m3)K3. Then m1+m2+m32, so ΔΔ. It contradicts to <ΔΔ. 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:

  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.