On graphs with graphic imbalance sequences
The imbalance of the edge e = uv in a graph G is the value imbG(e) = |dG(u) − dG(v)|. We prove that the sequence MG of all edge imbalances in G is graphic for several classes of graphs including trees, graphs in which all non-leaf vertices form a clique and the so-called complete extensions of paths...
Збережено в:
| Дата: | 2014 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Інститут прикладної математики і механіки НАН України
2014
|
| Назва видання: | Algebra and Discrete Mathematics |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/153349 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | On graphs with graphic imbalance sequences / S. Kozerenko, V. Skochko // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 1. — С. 97–108. — Бібліогр.: 10 назв. — англ. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-153349 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1533492019-06-15T01:26:57Z On graphs with graphic imbalance sequences Kozerenko, S. Skochko, V. The imbalance of the edge e = uv in a graph G is the value imbG(e) = |dG(u) − dG(v)|. We prove that the sequence MG of all edge imbalances in G is graphic for several classes of graphs including trees, graphs in which all non-leaf vertices form a clique and the so-called complete extensions of paths, cycles and complete graphs. Also, we formulate two interesting conjectures related to graphicality of MG. 2014 Article On graphs with graphic imbalance sequences / S. Kozerenko, V. Skochko // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 1. — С. 97–108. — Бібліогр.: 10 назв. — англ. 1726-3255 2010 MSC:05C07, 05C99. http://dspace.nbuv.gov.ua/handle/123456789/153349 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
The imbalance of the edge e = uv in a graph G is the value imbG(e) = |dG(u) − dG(v)|. We prove that the sequence MG of all edge imbalances in G is graphic for several classes of graphs including trees, graphs in which all non-leaf vertices form a clique and the so-called complete extensions of paths, cycles and complete graphs. Also, we formulate two interesting conjectures related to graphicality of MG. |
| format |
Article |
| author |
Kozerenko, S. Skochko, V. |
| spellingShingle |
Kozerenko, S. Skochko, V. On graphs with graphic imbalance sequences Algebra and Discrete Mathematics |
| author_facet |
Kozerenko, S. Skochko, V. |
| author_sort |
Kozerenko, S. |
| title |
On graphs with graphic imbalance sequences |
| title_short |
On graphs with graphic imbalance sequences |
| title_full |
On graphs with graphic imbalance sequences |
| title_fullStr |
On graphs with graphic imbalance sequences |
| title_full_unstemmed |
On graphs with graphic imbalance sequences |
| title_sort |
on graphs with graphic imbalance sequences |
| publisher |
Інститут прикладної математики і механіки НАН України |
| publishDate |
2014 |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/153349 |
| citation_txt |
On graphs with graphic imbalance sequences / S. Kozerenko, V. Skochko // Algebra and Discrete Mathematics. — 2014. — Vol. 18, № 1. — С. 97–108. — Бібліогр.: 10 назв. — англ. |
| series |
Algebra and Discrete Mathematics |
| work_keys_str_mv |
AT kozerenkos ongraphswithgraphicimbalancesequences AT skochkov ongraphswithgraphicimbalancesequences |
| first_indexed |
2025-07-14T04:34:10Z |
| last_indexed |
2025-07-14T04:34:10Z |
| _version_ |
1837595519990366208 |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 18 (2014). Number 1, pp. 97 – 108
© Journal “Algebra and Discrete Mathematics”
On graphs with graphic imbalance sequences
Sergiy Kozerenko and Volodymyr Skochko
Communicated by V. V. Kirichenko
Abstract. The imbalance of the edge e = uv in a graph G
is the value imb G(e) = |dG(u)−dG(v)|. We prove that the sequence
MG of all edge imbalances in G is graphic for several classes of
graphs including trees, graphs in which all non-leaf vertices form a
clique and the so-called complete extensions of paths, cycles and
complete graphs. Also, we formulate two interesting conjectures
related to graphicality of MG.
Introduction
The notion of edge imbalance was introduced in 1997 by Albertson [2]
as a measure of irregularity of a graph. By definition irregularity of G is
the following value:
I(G) =
∑
uv∈E(G)
|dG(u) − dG(v)|.
There is quite extensive literature on graphs irregularity (see [1–3,5–10]
and references therein), which primarily consists of finding upper and lower
bounds on I(G). However, it seems like no author studied the sequence of
edge imbalances in graphs as the main object. We hope that the present
paper will open up things in this direction.
We consider only simple, finite and undirected graphs. By V (G) and
E(G) we denote the vertex set and the edge set of a graph G respectively.
2010 MSC: 05C07, 05C99.
Key words and phrases: edge imbalance, graph irregularity, graphic sequence.
98 Graphic imbalance sequences
Two vertices u, v ∈ V (G) are adjacent if they are joined by an edge,
i.e. if uv ∈ E(G). Two graphs G1 and G2 are isomorphic if there exists
adjacency preserving bijection φ : V (G1) → V (G2). We write G1 ≃ G2 if
G1 and G2 are isomorphic.
The neighborhood of a vertex u ∈ V (G) in a graph G is the set
NG(u) = {v ∈ V (G) : uv ∈ E(G)}. The degree dG(u) of a vertex u in G
is the number of its neighbors, i.e. dG(u) = |NG(u)|. A graph G is called
regular if every vertex from G has the same degree.
The vertex u ∈ V (G) is called isolated if dG(u) = 0. Further, the
vertex u ∈ V (G) is called a leaf if dG(u) = 1. The set of all leaves in G is
denoted by L(G).
The set of vertices U ⊂ V (G) is called clique if every two vertices
u, v ∈ U are adjacent in G. A matching in a graph is a set of edges without
common vertices.
A graph is connected if each pair of vertices is joined by a path.
Otherwise graph is called disconnected. A maximal connected subgraph of
a given graph G is called its connected component. The vertex u ∈ V (G) is
a cut-vertex if its deletion increases the number of connected components
in G. A tree is a connected acyclic graph.
As usual, by Kn, K1,n−1, Pn and Cn we denote the complete graph,
star, path and cycle with n vertices respectively. Note that by definition
K1,0 = K1.
The complement of a graph G is a graph G with V (G) = V (G) and
uv ∈ E(G) if uv /∈ E(G). The empty graph is a complement of complete
graph.
Now let G1 and G2 be two graphs with disjoint vertex sets. The union
of G1 and G2 is the graph G = G1 ∪ G2 with V (G) = V (G1) ∪ V (G2)
and E(G) = E(G1) ∪ E(G2). We write mH for the union ∪m
i=1Gi with
Gi ≃ H, 1 6 i 6 m.
Similarly, the join of G1 and G2 is the graph G = G1 + G2 with
V (G) = V (G1)∪V (G2) and E(G) = E(G1)∪E(G2)∪{uv : u ∈ V (G1), v ∈
V (G2)}.
The imbalance of the edge e = uv in a graph G is the value imb G(e) =
|dG(u) − dG(v)|. The multiset of all edge imbalances in G is denoted by
MG. Note that irregularity I(G) =
∑
MG is even for every graph G.
Now suppose we have a finite sequence M (or more correctly, a multiset)
of nonnegative integers. The sequence M is called graphic if it is the degree
sequence of some graph G. Every such graph G is called a realization
of M . A well-known Erdos-Gallai theorem [4] states that the sequence
S. Kozerenko, V. Skochko 99
M = {a1 > · · · > an} is graphic if and only if the sum
∑
M is even and
r
∑
i=1
ai 6 r(r − 1) +
n
∑
i=r+1
min{r, ai}.
for all 1 6 r 6 n − 1.
We associate with every finite sequence of integers M = {a1, . . . , an}
the function fM : Z → Z in the following way:
fM (m) = |{1 6 i 6 n : ai = m}|.
Also, by convention m[n] denotes the sequence a1, . . . , an where ai = m
for all 1 6 i 6 n. Thus, for example {1[2], 2[3]} = {1, 1, 2, 2, 2}. Note that
the sequence M = {m[n]} is graphic if and only if m 6 n − 1 and mn is
even.
1. Results
Firstly, we formulate some easy properties of graphs whose imbalance
sequences are graphic.
Proposition 1. Let G, G1, G2 be graphs. Then
1) if MG1 and MG2 are graphic, then so is MG1∪G2;
2) if MG is graphic, then MK1+G is also graphic;
3) if G is a graph with constant edge imbalance, then MG is graphic;
Proof. 1) Just observe that MG1∪G2 = MG1 ∪ MG2 .
2) If H is a realization of MG, then it is easy to see that H ∪ G is a
realization of MK1+G.
3) If imb G(e) = m 6 |E(G)| − 1 for all edges e ∈ E(G), then since
I(G) =
∑
MG = m|E(G)| is always even, the sequence MG is
graphic.
Theorem 1. If T is a tree, then MT is graphic.
Proof. Let T be a tree with n > 1 vertices. Firstly, suppose that |V (T ) −
L(T )| = 0. Then T ≃ K2 and MT = {0} is obviously graphic. Similarly,
if |V (T ) − L(T )| = 1, then T ≃ K1,n−1 and MT = {n − 2[n − 1]} is also
graphic.
100 Graphic imbalance sequences
Further the proof goes by induction on n. If n = 1, then T ≃ K1 and
MT = ∅ is trivially graphic. Now let T be a tree with n > 2 vertices. If
|V (T ) − L(T )| 6 1, then we are done. If |V (T ) − L(T )| > 2, then there
exists a vertex v ∈ V (T ) that adjacent to dT (v) − 1 leaves in T . Thus
there exists a unique non-leaf vertex u ∈ V (T ) adjacent to v.
Now consider a tree T ′ = T − (NT (v) ∩ L(T )). It is easy to check that
MT = (MT ′ − {dT (u) − 1}) ∪ {|dT (u) − dT (v)|, dT (v) − 1[dT (v) − 1]}.
By induction hypothesis MT ′ is graphic. Let H be its realization. Fix a
vertex x ∈ V (H) with dH(x) = imb T ′(uv) = dT (u) − 1. We consider two
cases.
Case 1: dT (u) > dT (v).
Add to H dT (v) − 1 new vertices x1, . . . , xdT (v)−1 with edges xixj for
1 6 i, j 6 dT (v) − 1. Further, fix dT (v) − 1 neighbors y1, . . . , ydT (v)−1 ∈
NH(x) of x in H. Delete each edge xyi, 1 6 i 6 dT (v) − 1 and add new
edges xiyi for 1 6 i 6 dT (v) − 1. Obtained graph is a realization of MT .
Case 2: dT (u) 6 dT (v) − 1.
Let NH(x) = {x1, . . . , xdT (u)−1}. Delete each edge xxi, 1 6 i 6
dT (u) − 1 from H. Now add dT (v) − 1 new vertices y1, . . . , ydT (v)−1 with
new edges yiyj for 1 6 i, j 6 dT (v)−1 and xyk for dT (u) 6 k 6 dT (v)−1.
Also, add new edges xkyk for 1 6 k 6 dT (u) − 1. Again, obtained graph
is a realization of MT .
Definition 1. A graph G is called cl-graph if V (G) − L(G) induces a
clique in G.
It is easy to see that if G is disconnected cl-graph, then G ≃ H ∪mK2,
where H is a connected cl-graph. Therefore MG is graphic if and only if
MH is graphic.
Theorem 2. If G is a connected cl-graph graph, then MG is graphic.
Proof. Let V (G) − L(G) = {v1, . . . , vn}. The proof goes by induction
on n. If n = 1, then G is a star and MG is graphic by Theorem 1.
Now for every 1 6 i 6 n consider the following value:
li = |NG(vi) ∩ L(G)|.
At first suppose that there exists 1 6 i0 6 n such that li0 = 0. In this
case the vertex vi0 will be called bald.
From induction hypothesis it follows that MG−vi0
is graphic. Sup-
pose H its realization. Fix a bijection f : E(G − vi0) → V (H) with
S. Kozerenko, V. Skochko 101
dH(f(e)) = imb G−vi0
(e) for all edges e ∈ E(G − vi0). Add n − 1 new
vertices x1, . . . , xn−1 with new edges xif(e) for all e = viu, where u ∈
L(G − vi0), 1 6 i 6 n − 1. It is easy to see that obtained graph is a
realization of MG.
Now let li > 1 for all 1 6 i 6 n. It means that for every 1 6 i 6 n
one can choose a vertex ui ∈ NG(vi) ∩ L(G). Consider the graph G′ =
G−{u1, . . . , un}. We now show that if MG′ is graphic, then MG is graphic
too.
Suppose that H ′ is a realization of MG′ . Fix a bijection g : E(G′) →
V (H ′) with dH′(g(e)) = imb G′(e) for all edges e ∈ E(G′). Add n new
vertices x1, . . . , xn with new edges xixj , 1 6 i, j 6 n and xkf(e) for all
e = vku, where u ∈ L(G′), 1 6 k 6 n. Again, the obtained graph is a
realization of MG.
Therefore one can always reduce a cl-graph G to a cl-graph G0 with a
bald vertex. But we have already proved that in this case MG0 is graphic.
Thus for every cl-graph G the sequence MG is graphic.
Let G be a graph with n vertices and a : V (G) → Z+ be a function
with a(v) > dG(v) for all v ∈ V (G).
Take n complete graphs Gv ≃ Ka(v), v ∈ V (G) with disjoint vertex
sets. Since a(v) > dG(v), for every v ∈ V (G) there exists injective map
φv : NG(v) → V (Gv). A complete extension of G is a graph G(a) which
is obtained by taking the union of Gv, v ∈ V (G) and adding new edges
between φv1(u1) and φv2(u2) whenever v1v2 ∈ E(G) and u1 = v2, u2 = v1.
One can think of complete extension as of graph which is obtained
from G by replacing each vertex v ∈ V (G) with a complete graph of
sufficiently large order.
Example 1. Fig. 1 shows a complete extension of the path P3 = {v1 −
v2 − v3} for a(v1) = 2, a(v2) = 3, a(v3) = 1.
•
• • • • •
Figure 1. Complete extension of P3.
Proposition 2. Let G be a complete extension of a path Pn, n > 1. Then
MG is graphic.
102 Graphic imbalance sequences
Proof. Let V (Pn) = {v1, . . . , vn}, E(Pn) = {vivi+1 : 1 6 i 6 n − 1} and
G = Pn(a), where a : V (Pn) → Z+ with a(vi) > 2 for all 2 6 i 6 n − 1
and a(v1) > 1, a(vn) > 1.
Put ai = a(vi) for each 1 6 i 6 n. We use induction on n.
If n = 1, then G is a complete graph and thus MG = {0, . . . , 0} is
graphic.
Now let n > 2. Consider a path Pn−1 = Pn − {vn} with a′ being
restriction of a to V (Pn−1) and put G′ = Pn−1(a′). One can check that
MG = (MG′ − {0[an−1 − 2], 1})
∪
{
0[1 +
(an − 1)(an − 2)
2
], 1[an + an−1 − 3], |an−1 − an|
}
.
From induction hypothesis it follows that MG′ is graphic. Suppose
that H its realization. Fix a leaf x′ ∈ L(H) and delete the corresponding
edge x′x0 from H. Further, fix an−1 −2 isolated vertices x1, . . . , xan−1−2 ∈
V (H). Now add a new vertex y and an − 1 new vertices y1, . . . , yan−1.
Also, add k = (an−1)(an−2)
2 new isolated vertices z1, . . . , zk.
We consider two cases.
Case 1: an − 1 > an−1 − 2.
Add new edges xiyi for all 1 6 i 6 an−1 − 2. Also, add new edges yyi
for an−1 − 1 6 i 6 an − 2. Finally, add a new edge between x0 and yan−1.
Obtained graph is a realization of MG.
Case 2: an−1 − 2 > an.
Add new edges yixi for all 1 6 i 6 an − 1. Also, add new edges yxi
for an 6 i 6 an−1 − 2. Finally, add a new edge between y and x0. Again,
the obtained graph is a realization of MG.
To prove analogous results for complete extensions of cycles and com-
plete graphs we use a simple lemma which is a straightforward consequence
of Erdos-Gallai criterion.
Lemma 1. Let M be a sequence of nonnegative integers such that
∑
M
is even and 2fM (1) >
∑
M . Then M is graphic.
Proposition 3. Let G be a complete extension of a cycle Cn, n > 3.
Then MG is graphic.
Proof. Let V (Cn) = {v1, . . . , vn}, E(Cn) = {vivi+1 : 1 6 i 6 n − 1} ∪
{v1vn} and G = Cn(a), where a : V (G) → Z+ with a(vi) > 2 for all
1 6 i 6 n.
S. Kozerenko, V. Skochko 103
Now put ai = a(vi) for each 1 6 i 6 n. Using induction on n we prove
that the following inequality holds.
2
n
∑
i=1
ai − 4n >
n−1
∑
i=1
|ai − ai+1| + |an − a1|. (1)
Firstly, suppose that n = 3. Without loss of generality we can assume
that a1 > a2 > a3. We have
(a1 − a2) + (a2 − a3) + (a1 − a3) = 2a1 − 2a3
= 2(a1 + a2 + a3) − 2a2 − 4a3
6 2(a1 + a2 + a3) − 12.
Now let n > 4. Further the proof splits into two casses.
Case 1: There exists 1 6 k 6 n such that ak−1 6 ak 6 ak+1, where
k − 1 and k + 1 taken modulo n.
Without loss of generality we can assume that k = n. Therefore, let
an−1 6 an 6 a1. Using induction hypothesis and inequality an > 2 we
obtain
2
n
∑
i=1
ai − 4n > 2
n−1
∑
i=1
ai − 4(n − 1)
>
n−2
∑
i=1
|ai − ai+1| + |an−1 − a1|
=
n−2
∑
i=1
|ai − ai+1| + |an−1 − an| + |an − a1|
=
n−1
∑
i=1
|ai − ai+1| + |an − a1|.
Case 2: For all 1 6 k 6 n we have ak−1 6 ak > ak+1 or ak−1 > ak 6
ak+1.
In this case n is even as Cn should be bipartite. Furthermore, it holds
that a1 6 a2 > · · · 6 an > a1 or a1 > a2 6 · · · > an 6 a1. Assume that
a1 6 a2. Then
2
n
2
∑
i=1
|ai − ai+1| + |an − a1| = 2
n
2
∑
i=1
(a2i − a2i−1).
104 Graphic imbalance sequences
Therefore
2
n
∑
i=1
ai − 4n − 2
n
2
∑
i=1
(a2i − a2i−1) = 4
n
2
∑
i=1
a2i − 4n > 4 · 2 ·
n
2
− 4n = 0.
Thus the inequality (1) holds. Now, it is easy to see that
fMG
(1) >
n
∑
i=1
(ai − 2) = 2
n
∑
i=1
ai − 4n.
On the other hand
∑
MG − fMG
(1) 6
n−1
∑
i=1
|ai − ai+1| + |an − a1|.
Thus 2fMG
(1) >
∑
MG and the desired follows from Lemma 1.
Proposition 4. Let G be a complete extension of complete graph Kn,
n > 1. Then MG is graphic.
Proof. Let V (Kn) = {v1, . . . , vn} and G = Kn(a), where a : V (G) → Z+
with a(vi) > n − 1 for all 1 6 i 6 n.
Put ai = a(vi) for each 1 6 i 6 n. Without loss of generality we
can assume that a1 > a2 > · · · > an. Again, our goal is to show that
2fMG
(1) >
∑
MG.
Firstly, observe that
fMG
(1) >
n
∑
i=1
(n − 1)(ai − n + 1)
and
∑
MG − fMG
(1) 6
∑
i,j
|ai − aj | =
n
∑
i=1
(n − 2i + 1)ai.
Therefore it is sufficient to show that
n
∑
i=1
(n − 1)(ai − n + 1) >
n
∑
i=1
(n − 2i + 1)ai. (2)
We have
n
∑
i=1
(n − 1)(ai − n + 1) =
n
∑
i=1
(n − 2i + 1)ai +
n
∑
i=1
(2i − 2)ai − n(n − 1)2.
S. Kozerenko, V. Skochko 105
Using ai > n − 1, 1 6 i 6 n we obtain
n
∑
i=1
(2i − 2)ai > 2(n − 1)
n
∑
i=1
(i − 1)
= 2(n − 1) ·
(n − 1)n
2
= n(n − 1)2.
Thus the inequality (2) holds and the desired follows from Lemma 1.
2. Conjectures
As it can be seen from Fig. 2 there exist graphs whose imbalance
sequences aren’t graphic.
•
• • • •
•
Figure 2. Graph whose imbalance sequence is not graphic.
In fact the following proposition is true.
Proposition 5. Let M be a finite sequence of nonnegative integers such
that
∑
M is even. Then there exists a graph G with MG −M = {0, . . . , 0}.
Proof. For every even m ∈ M construct a graph Gm in the following way.
Take any m + 1 - regular graph G such that G has a matching H of a
size m
2 (for example G = Km+1,m+1). Then delete all edges E(H) from
G and add a new vertex v with new edges from v to V (H). Then again
add a new vertex u and a new edge uv to obtain a graph Gm. Clearly,
MGm
= {m, 0, . . . , 0}.
Now since
∑
M is even, the number of odd integers m ∈ M is even.
Divide the multiset of odd integers from M into pairs. For every such
pair {m1, m2} take any m1 + m2 + 1 - regular graph G′ with matching
H ′ of a size m1+m2
2 . Again, delete all edges E(H ′) from G′ and add two
new vertices v1, v2 with new edges from v1 to m1 vertices from V (H ′) and
new edges from v2 to remaining m2 vertices from V (H ′). Finally, add two
new vertices u1, u2 with new edges u1v1, u2v2 to obtain a graph Gm1,m2 .
It is easy to see that MGm1,m2
= {m1, m2, 0, . . . , 0}.
106 Graphic imbalance sequences
Now take G as a union of Gm and Gm1,m2 for all even m ∈ M and all
pairs {m1, m2} of odd integers from M . Clearly MG = M ∪{0, . . . , 0}.
The following conjecture originally appears on MathOverflow (question
name “Graphs with graphic imbalance sequences”).
Imbalance conjecture: Suppose that for all edges e ∈ E(G)
we have imb G(e) > 0. Then MG is graphic.
Remark 1. This conjecture was verified for all such graphs with 6 9
vertices.
Also, note that since for all graphs G the irregularity I(G) =
∑
MG is
always even, then MG is always pseudographic, i.e. it is the degree sequence
of some pseudograph (multiple edges and loops allowed). Furthermore, if
G has no vertices with zero imbalance, then I(G) =
∑
MG > max MG +
|E(G)| − 1 > 2 max MG. This means that MG is multigraphic, i.e. it is
the degree sequence of some multigraph (only multiple edges allowed).
The Imbalance conjecture naturally generalizes these facts.
To formulate our second conjecture we need to consider the mean
imbalance of every nonempty graph G. By definition it is the following
value:
m(G) =
I(G)
|E(G)|
.
Here are some properties of mean imbalances.
Proposition 6. Let G be a nonempty graph. Then
1) m(G) = 0 if and only if every component of G is regular;
2) m(G) 6 |E(G)| − 1;
3) for every q ∈ Q+ there exists a graph G with m(G) = q.
Proof. 1) It is easy.
2) Follows from the inequality I(G) 6 |E(G)|(|E(G)| − 1).
3) If q ∈ Q+, then q = a
b
for a, b ∈ Z+. Put G = K1,a+1∪(a+1)(b−1)K2.
We have
m(G) =
a(a + 1)
a + 1 + (a + 1)(b − 1)
=
a
b
= q.
S. Kozerenko, V. Skochko 107
Now observe that if the imbalance of every edge in G is nonzero,
then m(G) > 1. Sadly, this inequality can’t ensure the graphicality of
MG. However, we believe that there exists a “universal” constant c > 0
such that for every graph G with m(G) > c the sequence MG is graphic.
Moreover, we think that c = 2 because of the following result.
Proposition 7. The set of all mean imbalances of graphs with non-graphic
imbalance sequences is dense in [0, 2].
Proof. For every n ∈ N and 1 6 k 6 n construct a graph G(n,k) as
follows. Take a complete graph H ≃ K2n+2 with the vertex set V (H) =
{v1, . . . , v2n+2}. Delete from H every edge v2i−1v2i, 1 6 i 6 k and add
2k new vertices u1, . . . , u2k with new edges ujvj for 1 6 j 6 2k to
obtain G(n,k).
Since 1 6 k 6 n, the sequence MG(n,k) = {2n[2k]} is not graphic. We
have
m(G(n,k)) =
4nk
(n + 1)(2n + 1) + k
.
Now we show that the set {m(G(n,k)) : n ∈ N, 1 6 k 6 n} is dense in
[0, 2].
At first, observe that m(G(n,1)) → 0, n → ∞. Now let r ∈ (0, 2]. Since
r > 0, there exists n0 ∈ N such that for all n > n0 it holds that ⌊ rn
2 ⌋ > 1.
Furthermore, the inequality r 6 2 implies ⌊ rn
2 ⌋ 6 n for every n ∈ N. Now
it is easy to see that
m(G(nn0,⌊
rnn0
2
⌋)) → r, n → ∞.
Corollary 1. For every ε > 0 there exists a graph G with non-graphic
MG such that m(G) > 2 − ε.
Therefore we can formulate our final conjecture.
Conjecture: Suppose that for G we have m(G) > 2. Then
MG is graphic.
References
[1] H. Abdo, N. Cohen and D. Dimitrov, Bounds and computation of irregularity of a
graph // Preprint, arXiv:1207.4804 (2012).
[2] M. O. Albertson, The irregularity of a graph // Ars Comb. 46 (1997), 219-225.
[3] F. K. Bell, A note on the irregularity of graphs // Lin. Algebra Appl. 161 (1992),
45–54.
108 Graphic imbalance sequences
[4] P. Erdos, T. Gallai, Graphs with prescribed degrees of vertices // Mat. Lapok 11
(1960), 264–274.
[5] F. Goldberg, A spectral bound for graph irregularity // Preprint, arXiv:1308.3867
(2013).
[6] P. Hansen, H. Melot, Variable neighborhood search for extremal graphs 9. Bound-
ing the irregularity of a graph // DIMACS Ser. Discrete Math. Theoret. Comput.
Sci. 69 (2005), 253-264.
[7] M. A. Henning, D. Rautenbach, On the irregularity of bipartite graphs // Discrete
Math. 307 (2007), 1467-1472.
[8] M. Tavakoli, F. Rahbarnia, M. Mirzavaziri, A. R. Ashrafi and I. Gutman, Ex-
tremely irregular graphs // Kragujevac J. Mat. 37(1) (2013), 135-139.
[9] W. Luo, B. Zhou, On irregularity of graphs // Ars Comb. 88 (2008), 55-64.
[10] W. Luo, B. Zhou, On the irregularity of trees and unicyclic graphs with given
matching number // Util. Math. 83 (2010), 141-147.
Contact information
S. Kozerenko,
V. Skochko
Department of Mechanics and Mathematics,
Kyiv National Taras Shevchenko Univ.,
Volodymyrska str., 64, 01033 Kyiv, Ukraine
E-Mail: kozerenkosergiy@ukr.net,
vovaskochko@yandex.ua
Received by the editors: 14.05.2014
and in final form 14.05.2014.
|