Let be a connected graph with edges. The density of a nontrivial subgraph with components is . A graph is uniformly dense if for any nontrivial subgraph of , . For each cyclic ordering of , let be the largest integer such that every cyclically consecutive elements in induce a forest in ; and the largest , taken among all cyclic orderings of , is denoted by . A cyclic ordering of is a cyclic base ordering if . 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 . In this paper, we investigate the value of for some families of graphs and determine all connected graphs with .
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 , let be the number of connected
components of . Following the
notations in [3], define
the density and the fractional
arboricity as follows:
A graph is uniformly dense if
. 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 denote the number of edges
of . A sequence to list all the
edges in is a cyclic ordering of
if the subscripts of the sequence
are taken modulo . Let be the collection of all
cyclic ordering of . For each
, let
be the largest integer such that
every cyclically consecutive
elements in induces a forest in
, where a forest is a graph that
contains no cycles; and define . By definition, for any
loopless nontrivial graph . 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 is a
cyclic base ordering if . 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 be a
connected nontrivial graph on
vertices. If , then is uniformly dense.
Kajitani et al. in [15]
proposed the conjecture that if
is uniformly dense, then . Thus investigating the value of is of interests. The purpose of this
study is to investigate the relationship between the value of and the structural properties of
which may measure the closeness
for a graph 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 be a connected nontrivial
graph with vertices. Then every
cyclic ordering of is a cyclic
base ordering if and only if is
either a tree or a cycle.
Proof. We prove the sufficiency first. If is a tree, then . Clearly, for any cyclic
ordering of , and so it is a cyclic base
ordering. Now we suppose is a
cycle. We know and . Notice that every set of edges induces a path. Therefore, for
any cyclic ordering of , and so . Every cyclic ordering of is a cyclic base ordering.
We prove the necessity by contradiction. Suppose every cyclic
ordering of is a cyclic base
ordering but is neither a tree
nor a cycle. Since is connected,
and contains a cycle but . Without loss of generality, suppose and is a cycle of . Consider the cyclic ordering . We have because is a cycle and . However, by the assumption, it is a cyclic base ordering of
, so , a contradiction. This completes
the proof.
Suppose . Let , and . If there is no edge
between and , then and . Let .
We prove the following.
Lemma 2.2.
For every graph , if , then where .
Proof. Assume that . Suppose where . Then for any cyclic
ordering, every cyclically
consecutive elements induce a forest in , and contain at most one edge in . Then . It contradicts to
. Hence .
Corollary 2.3.
For a nontrivial graph , if and only if .
Proof. We prove the necessity first. It is known that . By Lemma 2.2, . Therefore, . It remains to prove the
sufficiency. Assume that . Suppose , where . Since and , we can put at least
one edge after and the edges
between and are different for and . Then we have a
cyclic ordering such that . It is a contradiction to . Thus .
3. Results
In this section, we study
of the complete graph on three vertices, denoted by , where multiple edges are allowed.
Also, we prove a formula for obtaining under a particular set of
constraints. Finally, we propose the structure for all graphs with and prove the necessity of
the conjecture.
Theorem 3.1.
Let be the graph where are the number of edges
between two vertices and . Then
Proof. Let , be the set of all edges with
endpoints and for , be the set of all edges with
endpoints and , and for . Then .
If , then
.
By Corollary 2.3, .
Now suppose . Let
. Then there exists a cyclic ordering such that the ordering alternates
between an edge from and an
edge from or . Since , there are at least as
many edges in as in
. So . Notice that . Therefore, .
Let be the graph obtained
from by combining all multiple
edges between two vertices to only one edge. Let be the girth of , which is the length of the shortest
cycle in . See Figure 1 for an
example. If is a tree, we
define .
Figure 1 and where
Theorem 3.2.
For a graph , suppose . Then each of the
following holds.
(i) If , then .
(ii) If , then .
Proof. Let , be the
set of all edges in that were
combined to in and where
for . Without loss of
generality, we suppose . For each cyclic ordering of , where , the edges in divide the ordering into intervals with the first
edges from .
If , since
, there is a cyclic
ordering such that each interval
has at least edges and no
multiple edges from the same
are in the same interval for . So .
This proves part .
Suppose . To prove by contradiction, assume that has a cyclic order with . The edges in
divide the ordering into intervals. If one such
interval has at most edges, then
length of this interval together with the edges from on both sides of the interval is at
most and it contains
a 2-cycle, contrary to . Hence, every interval must have at least edges. So .
Suppose . Let is a subgraph of . If , we define . Let .
We propose a structure for all graphs that satisfy and prove the necessity. Below, we
use for .
Conjecture 3.3.
Let be a connected graph. Then
if and only if .
Theorem 3.4.
Let be a connected graph. If
then .
Proof. If ,
then has no 3-cycle and . If , by Theorem
3.2, .
It is sufficient to prove the case when . If , then . By Lemma
2.2, . And by Corollary 2.3, . Therefore, . If , suppose satisfies . Since , by
the definition of .
Therefore, , i.e.
. By Corollary 2.3, . Assume that . Let be the cyclic ordering such that . Then every cyclically consecutive elements in
has at most two edges in . Then , so . It contradicts to
. Thus .
Acknowledgements
We would like to express our sincere gratitude to Dr. Hong-Jian Lai
for his introducing the concept of 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.
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.