Decomposition of Directed Graphs and the Turán Problem
We consider vertex decompositions of (di)graphs appearing in the automata theory and establish some properties of these decompositions. These decompositions are applied to the problem of forbidden subgraphs.
Gespeichert in:
| Datum: | 2014 |
|---|---|
| Hauptverfasser: | , , , , , |
| Format: | Artikel |
| Sprache: | Ukrainisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2014
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/2191 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860508138862542848 |
|---|---|
| author | Zholtkevich, G. N. Novikov, B. V. Polyakova, L. Yu. Жолткевич, Г. Н. Новіков, Б. В. Полякова, Л. Ю . |
| author_facet | Zholtkevich, G. N. Novikov, B. V. Polyakova, L. Yu. Жолткевич, Г. Н. Новіков, Б. В. Полякова, Л. Ю . |
| author_sort | Zholtkevich, G. N. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2019-12-05T10:25:58Z |
| description | We consider vertex decompositions of (di)graphs appearing in the automata theory and establish some properties of these decompositions. These decompositions are applied to the problem of forbidden subgraphs. |
| first_indexed | 2026-03-24T02:20:27Z |
| format | Article |
| fulltext |
UDC 519.171.1+519.176
B. V. Novikov, L. Yu. Polyakova, G. N. Zholtkevich (Karazin Nat. Univ., Kharkov, Ukraine)
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM
ОДИН РОЗКЛАД ОРIЄНТОВАНИХ ГРАФIВ I ЗАДАЧА ТУРАНА
We consider vertex decompositions of (di)graphs appearing in the Automata Theory and establish some properties of these
decompositions. We apply these decompositions to the problem of forbidden subgraphs.
Розглянуто вершиннi декомпозицiї (ор)графiв, що виникають у теорiї автоматiв, встановлено деякi їх властивостi, а
також наведено застосування їх до задачi про забороненi пiдграфи.
Introduction. This note has arisen from attempts to extend on pre-automata [1] the concepts of
regions and intervals used in the translation theory [2]. Unlike the known model, the uniqueness of
the header of an interval is an unacceptable condition for pre-automata. So we had to consider a
generalized problem; and it was convenient to collect obtained graph-theoretic results in a separate
article.
General definitions and results are given in Section 1. Regions and intervals are considered in
Section 2 as a special case. Next we study the decompositions of undirected graphs (Section 3) and
in particular consider their connection with maximal matchings. In Section 4 we study the main
application of decompositions — the problem of forbidden graphs. Note that this problem can be
posed also for digraphs. We hope that in this case our construction will be even more useful.
Mainly, we will use the definitions and notations of [3]. Thus by the directed graph (or digraph)
we mean a pair G = (V,E) where V = V (G) is a set whose elements are called vertices; E =
= E(G) ⊂ V × V is a binary relation whose elements are called arcs.
For every vertex v ∈ V define the sets D−(v) =
{
u ∈ V | (u, v) ∈ E
}
and D+(v) =
{
u ∈ V |
(v, u) ∈ E
}
whose elements are called the inputs and outputs of the vertex v respectively. Note that
loops are included both in D−(v) and D+(v).
The numbers of inputs and outputs are denoted by d−(v) and d+(v) respectively.
The subgraph of (di)graph G generated by a subset of vertices U ⊂ V is denoted by G[U ]. A
subset U ⊂ V is called connected if the graph G[U ] is connected (i.e., for any two vertices u, v ∈ U
there exists a directed path in G[U ] starting at u and ending at v).
The symbol
⊔
is used for the union of disjoint sets.
1. Inflation and stability. Let G = (V,E) be a digraph.
Definition 1.1. An inflation of a set U ⊂ V is a set
Inf U = U ∪
{
v ∈ V | ∅ 6= D−(v)∅U
}
.
We need a property of the inflation:
Proposition 1.1. For any subsets X,Y ⊂ V (G)
InfX ∩ Inf Y = (X ∩ Inf Y ) ∪ (InfX ∩ Y ) ∪ Inf (X ∩ Y ).
Proof. The inclusion ⊇ is obvious. Prove the converse. The case v ∈ X ∪ Y is also evident.
Let v ∈ (InfX ∩ Inf Y ) \ (X ∪ Y ). Then by the definition of inflation ∅ 6= D−(v) ⊂ X ∩ Y, i.e.,
v ∈ Inf (X ∩ Y ).
Proposition 1.1 is proved.
c© B. V. NOVIKOV, L. YU. POLYAKOVA, G. N. ZHOLTKEVICH, 2014
958 ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM 959
We can consider the operator Inf : 2V → 2V : U 7→ Inf U and its iterations Inf n, n > 0.
Suppose, in addition, Inf 0U = U.
Definition 1.2. A hyperinflation of a subset U is a set
Inf ∞U =
⋃
n≥0
Inf nU.
Sometimes we say that U is a hyperinflation if U = Inf ∞U ′ for some U ′.
The following statement will be used bellow:
Lemma 1.1. Let U ⊂ V and v ∈ V \ Inf ∞U. Then D+(v) ∩ Inf ∞U ⊂ U.
Proof. The case D+(v) ∩ Inf ∞U = ∅ is obvious. Let u ∈ D+(v) ∩ Inf ∞U 6= ∅, u 6∈ U. Then
u ∈ Inf nU = Inf (Inf n−1U) for some n ≥ 0. This contradicts the fact that D−(u) 3 v 6∈ Inf n−1U.
Lemma 1.1 is proved.
We define the notion of a hull which is close to the hyperinflation.
Definition 1.3. A set U ⊂ V is called stable if Inf U = U.
Lemma 1.2. An intersection of stable sets is stable.
Proof. Let Ui, i ∈ I, be stable sets, X =
⋂
i∈I
Ui, and v ∈ InfX \ X. By the definition of the
inflation ∅ 6= D−(v) ⊆ X ⊆ Ui for every i ∈ I. Therefore, v ∈ Inf Ui = Ui whence v ∈ X.
Lemma 1.2 is proved.
Since the set V of vertices is stable, we have the following corollary.
Corollary 1.1. For every vertex set U ⊆ V there exists the smallest stable set HullU contain-
ing U.
Definition 1.4. We say that HullU is the hull of a set U.
It is clear that HullU is the intersection of all stable sets containing U.
Consider connections between the introduced concepts. From U ⊂ Inf U it follows Inf ∞U ⊂
⊂ HullU. The reverse inclusion is true if and only if the hyperinflation is stable. The following
example shows that, generally speaking, for infinite digraphs this does not hold.
Example 1.1. Consider a digraph G = (V,E) such that
V = {0, 1, 2, . . .}, E =
{
(n, 0) | n ≥ 1
}
∪
{
(n, n+ 1) | n ≥ 1
}
.
Then Inf n{1} = {1, 2, . . . , n + 1}, whence Inf ∞{1} = V \ {0}. On the other hand, Hull {1} =
= Inf
(
Inf ∞{1}
)
= V.
Definition 1.5. We call a digraph G = (V,E) locally d−-finite if d−(v) <∞ for all v ∈ V.
Proposition 1.2. If a digraph G = (V,E) is locally d−-finite, then Inf ∞U = HullU for every
U ⊂ V.
Proof. Suppose the contrary. Let v ∈ Inf (Inf ∞U) \ Inf ∞U. As d−(v) <∞ and ∅ 6= D−(v) ⊆
⊆ Inf ∞U, we have D−(v) ⊂ Inf nU for some n ≥ 0. But then v ∈ Inf n+1U ⊂ Inf ∞U contrary to
assumption.
Proposition 1.2 is proved.
The statement similar to Lemma 1.1 is not true for the hull:
Example 1.2. Add the vertex −1 and the arc (−1, 0) to the digraph G from Example 1.1.
Obviously {0} = D−(−1) ∩Hull {1} 6= {1}.
Now we introduce the main definition of this article:
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
960 B. V. NOVIKOV, L. YU. POLYAKOVA, G. N. ZHOLTKEVICH
Definition 1.6. A decomposition of a digraph G = (V,E) is a set of its subgraphs Gi = (Vi, Ei),
i ∈ I, such that:
(i) Vi are hyperinflations,
(ii) V is a disjoint union of Vi,
(iii) Ei is a restriction of E to Vi.
Remark 1.1. Our definition differs from the one given, for example, in [4], where a decomposi-
tion means a partition of E(G).
Till the end of Section 2 we assume that some locally d−-finite graph G(V,E) is fixed.
Theorem 1.1. For any subsets X,Y ⊂ V
Inf ∞X ∩ Inf ∞Y = Inf ∞
[
(X ∩ Inf ∞Y ) ∪ (Inf ∞X ∩ Y )
]
.
Proof. The inclusion ⊇ is clear. Indeed,
(X ∩ Inf ∞Y ) ∪ (Inf ∞X ∩ Y ) ⊂ Inf ∞X ∩ Inf ∞Y ;
and the set Inf ∞X ∩ Inf ∞Y is stable because of the locally d−-finiteness of the original graph and
Lemma 1.2.
Let x ∈ Inf ∞X ∩ Inf ∞Y. Then there are integers m,n ≥ 0 such that x ∈ Inf mX ∩ Inf nY,
x 6∈ Inf m−1X ∪ Inf n−1Y, and
D−(x) ⊂ Inf m−1X ∩ Inf n−1Y ⊂ Inf ∞X ∩ Inf ∞Y.
Use the induction on m+ n to show that
x ∈ Inf ∞
[
(X ∩ Inf ∞Y ) ∪ (Inf ∞X ∩ Y )
]
. (1)
If m = 0 or n = 0, then x ∈ X ∪ Y ; hence (1) is hold.
If m = n = 1, then D−(x) ⊂ X ∩ Y. Therefore, x ∈ Inf (X ∩ Y ) ⊂ Inf ∞(X ∩ Y ) ⊂
⊂ Inf ∞
[
(X ∩ Inf ∞Y ) ∪ (Inf ∞X ∩ Y )
]
.
Consider the general case. Since D−(x) ⊂ Inf m−1X ∩ Inf n−1Y ⊂ Inf ∞X ∩ Inf ∞Y, by the
induction assumption
D−(x) ⊂ Inf ∞
[
(X ∩ Inf ∞Y ) ∪ (Inf ∞X ∩ Y )
]
.
Consequently (1) is true.
Theorem 1.1 is proved.
Corollary 1.2. Inf ∞X ∩ Inf ∞Y = ∅ if and only if
Inf ∞X ∩ Y = X ∩ Inf ∞Y = ∅.
As we will see below, the hyperinflations of connected subsets are of particular interest.
Theorem 1.2. Let X,Y ⊂ U, Inf ∞X∩Inf ∞Y 6= ∅, and X is connected. If Inf ∞X∩Y = ∅,
then Inf ∞X ⊂ Inf ∞Y.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM 961
Proof. Corollary 1.2 implies X∩Inf ∞Y 6= ∅. If X is a singleton, then the statement is obvious.
Let |X| > 1. We choose the smallest n such that X ∩ Inf nY 6= ∅ (it follows from the conditions
that n ≥ 1). Let x ∈ X ∩ Inf nY. Since x 6∈ Y, we have D−(x) ⊂ Inf n−1Y. But D−(x) ∩X 6= ∅,
because X is connected. Therefore, X ∩ Inf n−1Y 6= ∅; that contradicts the choice of n.
Theorem 1.2 is proved.
Theorem 1.2 allows us to construct (not uniquely) decompositions of finite graphs whose com-
ponents are hyperinflations of connected sets. Describe the process of constructing in detail.
Let V be a set of vertices of the graph. We take as V1 an arbitrary connected subset (for exam-
ple, a vertex). Suppose we have taken components V1, . . . , Vk with disjoint hyperinflations. In the
complement
U = V \
⊔
i≤k
Inf ∞Vi
choose an arbitrary connected subset W. If Inf ∞W ∩ Inf ∞Vj 6= ∅ for some 1 ≤ j ≤ k, then
Inf ∞Vj ⊂ Inf ∞W by Theorem 1.2. In this case replace all Vj by W and go on to the choice of the
next component. If Inf ∞W ∩
⊔
i≤k
Inf ∞Vi = ∅, then we put Vk+1 = W and continue the process.
2. Regions and intervals. Using the terminology of Computer Science [2] we introduce the
following definition.
Definition 2.1. A subset U ⊂ V is said to be a region if U = Inf ∞{x} for some x ∈ V. In
this case x is called a heading of U. A region is called an interval if it is not contained in any other
region.
Generally speaking, the region can have multiple headings. A sufficient condition for the unique-
ness of the heading (this demand is essential for Computer Science) is obtained directly from
Lemma 1.1:
Proposition 2.1. Let U ⊂ V be a region with a heading x. If there exists y ∈ V \ U such that
D+(y) ∩ U 6= ∅, then x is uniquely defined, i.e., D+(y) ∩ U = {x}.
Since a singleton is connected, it follows directly from Theorem 1.2:
Proposition 2.2. If two regions have a nonempty intersection, then one of them contains the
other.
Now we can state the main result about intervals of finite digraphs:
Theorem 2.1. Every digraph G = (U,E) with the finite set of vertices has the unique decom-
position whose components are intervals.
Proof. The existence of such a decomposition follows directly from Proposition 2.2; the unique-
ness follows from the maximality of each interval.
Consider two extreme cases.
Proposition 2.3. All components of an interval decomposition of a digraph are singletons if and
only if d−(v) = 1 implies D−(v) =
{
(v, v)
}
for any vertex v.
Proof. Let G = (V,E) be a considered digraph. It is clear that all its components are singletons
if and only if
∣∣Inf {v}∣∣ = 1 for all v ∈ V. If d−(v) = 1 and D−(v) 6=
{
(v, v)
}
, then there is a vertex
u 6= v such that (u, v) ∈ E and v ∈ Inf {u}. This implies
∣∣Inf {u}∣∣ > 1.
Conversely, suppose that the restriction on D− from the proposition conditions is hold and∣∣Inf {v}∣∣ > 1 for some v. If u ∈ Inf {v} \ {v}, then by definition of inflation d−(v) = 1; in
addition, the arc from D−(v) can not be a loop.
Proposition 2.3 is proved.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
962 B. V. NOVIKOV, L. YU. POLYAKOVA, G. N. ZHOLTKEVICH
Now assume that G = (V,E) is finite and its decomposition consists of only one component,
i.e., digraph is an interval. Let x be a heading of this interval (in general, not the only one), i.e.,
G = Inf ∞{x} = Inf n{x} for some n > 0.
Definition 2.2. A finite digraph H = (W,F ) with a partition W =
⊔n
i=1
Wi, n ∈ N, is called
a jet if it satisfies the following conditions:
(i) if i ≤ j, then (Wj ×Wi) ∩ F = ∅;
(ii) for each j ≥ 2 and every vertex x ∈ Wj there exist yi ∈ Wi, 1 ≤ i < j, forming a directed
path
y1 → y2 → . . .→ yj−1 → x.
Proposition 2.4. Let H = (W,F ) be a jet, x be an element not contained in W, and V =
= W ∪ {x}. Choose an arbitrary subset
C ⊂
⊔
i>1
(
Wi × {x}
)
∪
{
(x, x)
}
and put E = F ∪C ∪
(
{x}×W1
)
. Then in the digraph G = (V,E) the subset V is an interval with
a heading x.
Proof. Denote W0 = {x}, Zj =
⊔j
i=0
Wi and verify that Zj = Inf Zj−1. The inclusion ⊇ is
evident. Conversely, suppose that y ∈Wj , j > 0. By condition (ii) of Definition 2.2 D−(y) 6= ∅. By
condition (i) z ∈ D−(y) implies z ∈Wk for some k < j. It means that D−(y) ⊂ Zj−1.
It is easy to see that Inf {x} = W1; and thus V = Inf n{x} = Inf ∞{x}.
Proposition 2.4 is proved.
The converse is true. Moreover:
Proposition 2.5. Let
{
Gj = (Vj , Ej) | 1 ≤ j ≤ N
}
be an interval decomposition of a finite
digraph G = (V,E) and Vj = Inf ∞{xj}. Then every subgraph
(
Vj \ {xj}, Ej |Vj\{xj}
)
with the
partition
Vj \ {xj} =
∞⊔
ij=1
(
Inf ij{xj} \ Inf ij−1{xj}
)
is a jet.
Proof. Consider an interval Vk and put Wi = Inf i{xk}\ Inf i−1{xk}. If (u, v) ∈ (Wj×Wi)∩E
for 1 ≤ i ≤ j then v ∈ D+(u) 6⊂ Inf i−1{xk}. Hence for Vj \ {xj} condition (i) of Definition 2.2 is
hold. Condition (ii) is obvious.
3. Undirected graphs. In this section we assume that G = (V,E) is a finite undirected con-
nected graph without loops. We will use the notations D(v) and d(v) instead of D±(v) and d±(v)
respectively.
In the undirected case the description of a hyperinflation is simplified:
Proposition 3.1. Inf ∞U = Inf U for every subset U ⊂ V.
Proof. Let x ∈ Inf ∞U \ U. Then x ∈ Inf nU for some n ≥ 1 and (y, x) ∈ E for some
y ∈ Inf n−1U. But this is impossible for n > 1, otherwise, x ∈ D+(y) = D−(y) ⊂ Inf n−2U.
Therefore, n = 1 and x ∈ Inf U.
Proposition 3.1 is proved.
Thus in what follows we may talk about the inflation rather than the hyperinflation and use the
appropriate notations.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM 963
Consider some variants of decompositions. We will write them in the form of
V =
(⊔
i
Inf Vi
)
t U, (2)
where G[Vi] are graphs of some (fixed) class and U is a subset of singleton components.
First, in the process described after Theorem 1.2 we can choose nonsingleton connected sub-
sets as Vj until this is possible. Let components V1, . . . , Vk be chosen in such way and in U =
= V \
⊔
i≤k
Inf Vi there are no any connected components other than vertices. It means that U is
completely disconnected. Moreover D(v) ⊂ Vi for every v ∈ Inf Vi \ Vi. This proves the following
proposition.
Proposition 3.2. Each connected graph G = (V,E) with a finite set of vertices has the decom-
position of form (2) where Vi are nonsingleton connected subsets and U is completely disconnected
(possibly empty). Moreover
(⊔
i
Inf Vi \ Vi
)
∪ U is completely disconnected subset.
Another type of a decomposition is obtained if we choose two-element connected subsets, i.e.,
arcs, as V1, . . . , Vk. Clearly, the proof will not change, and we get the following corollary.
Corollary 3.1. Each connected graph G = (V,E) with a finite set of vertices has the decompo-
sition of form (2) where Vi are arcs1, U is completely disconnected (possibly empty) subset as well
as
(⊔
i
Inf Vi \ Vi
)
∪ U.
Recall that a matching of a graph is a set of pairwise nonadjacent edges, i.e., the arcs that have
no common vertices. A matching is said to be maximal, if it is not contained in any other matching
of the graph, and is said to be the greatest, if it contains the maximum number of arcs.
Decompositions of Corollary 3.1 are characterized in terms of matchings:
Theorem 3.1. For a finite connected graph G = (V,E) with the decomposition of form (2)
satisfying the conditions of Corollary 3.1 the arcs V1, V2, . . . form the maximal matching. Conversely,
if {V1, V2, . . .} is a maximal matching, then expression (2) is a decomposition satisfying the conditions
of Corollary 3.1.
Proof. By construction different Vi and Vj have no common vertices, therefore {V1, V2, . . .} is a
matching. The complete disconnectedness of(⊔
i
Inf Vi \ Vi
)
∪ U
implies its maximality.
Conversely, let {V1, V2, . . .} be a maximal matching and Vi = (xi, yi). Suppose that Inf Vi ∩
∩ Inf Vj 6= ∅, i 6= j. According to Corollary 1.2 we can assume that Inf Vi ∩ Vj 6= ∅. Since
Vi ∩ Vj = ∅, either xj or yj is contained in Inf Vi \ Vi.
If, for example, xj ∈ Inf Vi \ Vi, then yj ∈ D−(xj) ⊂ Vi; that is impossible. Similarly yj ∈
∈ Inf Vi \ Vi implies xj ∈ Vi. Hence Inf Vi ∩ Inf Vj = ∅ for all i 6= j.
Theorem 3.1 is proved.
We deal with another variant of a decomposition in the next section.
1We identify here an arc and the connected set of its vertices.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
964 B. V. NOVIKOV, L. YU. POLYAKOVA, G. N. ZHOLTKEVICH
4. Forbidden subgraphs. In this section we apply a decomposition to the well-known forbidden
subgraphs problem. This direction began with Turán’s work [5] about the number of edges in the
graph that does not contain any clique of given order. A good overview is given in [3]. Among the
recent articles we mention also [6].
In general, the problem statement is as follows:
Let H be a fixed finite graph (forbidden graph). Find the least upper bound ex(p,H) for the
number of arcs of finite graphs with p vertices, not containing H as a subgraph (such graphs are
called H-free).
We use the number-theoretic functions “floor” bxc, “ceiling” dxe, and fractional part {x}. Recall
that
bxc = x− {x}, dxe = x+ {−x}.
For K3 (the complete graph of order 3) ex(p,K3) =
⌊
p2
4
⌋
[3] (Theorem I.2). We obtain a similar
evaluation for the graph H of the form
• •
•
• •
@
@@
�
��
�
��
@
@@
Hereinafter H denotes just this graph. Following [4] we call it a “bowtie”.
A sequence of different vertices U = {v1, . . . , vn} ⊂ V of G(V,E) is said to be a path if
(vi, vi+1) ∈ E for all 1 ≤ i < n.
If U1, U2 are two disjoint subsets of vertices, then d(U1, U2) denotes the number of arcs con-
necting vertices of U1 with those of U2.
The volume of G = (V,E) is a pair volG = (p, q) where p is a number of vertices and q is a
number of arcs in G.
Our main result in this section is the following theorem.
Theorem 4.1. ex(p,H) =
⌊
p2
4
⌋
+ 1 for p > 4.
To build an H-free graph with exactly
⌊
p2
4
⌋
+ 1 arcs, it is sufficient to consider K⌊p
2
⌋
,
⌈p
2
⌉ (the
complete bipartite graph with partite sets containing
⌊p
2
⌋
and
⌈p
2
⌉
vertices
)
and to draw one more
arc in one of its partite sets.
The example of the graph K4 shows that for p = 4 the statement of Theorem 4.1 is violated.
The remaining part of the article will be devoted to the proof of the proposition which implies,
taking into account the facts mentioned above, the theorem.
Proposition 4.1. Let G be an H-free graph which is not isomorphic to K4 and volG = (p, q).
Then q ≤ p2
4
+ 1.
First, make sure that it is enough to prove this statement for connected graphs.
Lemma 4.1. Let G be a disconnected graph, volG = (p, q) and Gj , j = 1, . . . , n, n ≥ 2, be
all of its connected components with the volumes volGj = (pj , qj). If qj ≤
p2j
4
+ 1 for all j, then
q ≤ p2
4
+ 1.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM 965
Proof. It is clear that we can consider only the case n = 2. If p1 = p2 = 1 then q1 = q2 = 0,
and the lemma is true. Otherwise, p1p2 ≥ 2 implies
(p1 + p2)
2
4
+ 1 ≥
(
p21
4
+ 1
)
+
(
p22
4
+ 1
)
.
Lemma 4.1 is proved.
In what follows we assume that G is a finite and connected graph and do not indicate that
specially.
Prove some auxiliary statements.
Lemma 4.2. Let G = (V,E) be an H-free graph, U = {v1, . . . , vl} be a path in G and
x ∈ V \ U. Then d(x, U) ≤
⌈
l
2
⌉
+ 1. If the equality holds, then:
(i) there exist vertices vj , vj+1 adjacent to x;
(ii) either v1 or vl is adjacent to x, if l is even;
(iii) both v1 and vl are adjacent to x, if l is odd.
Proof. Let l be even, l = 2m. Suppose that d(x, U) ≥
⌈
l
2
⌉
+ 2 = m + 2. By the pigeonhole
principle among m pairs (v1, v2), (v3, v4), . . . , (v2m−1, v2m) there exist (vi, vi+1), (vj , vj+1) such
that four arcs outgoing from x end in them. At the same time i 6= j+1, j 6= i+1, hence x, vi, vi+1,
vj , vj+1 form a subgraph isomorphic to H.
If there are no vj , vj+1 adjacent to x, then d(x, U) ≤ m <
⌈
l
2
⌉
+ 1. This implies (i) for even l.
Since for the path U ′ = {v2, . . . , vl−1} consisting of l − 2 vertices d(x, U ′) ≤
⌈
l − 2
2
⌉
+ 1 =
=
⌈
l
2
⌉
, it follows from d(x, U) =
⌈
l
2
⌉
+ 1 that either v1 or vl is adjacent to x; therefore (ii) is
hold.
Let l = 2m+1. As it was proved above, for U ′ = {v1, . . . , v2m} the inequality d(x, U ′) ≤ m+1
holds. Hence d(x, U) ≤ m + 2 =
⌈
l
2
⌉
+ 1; and the equality is possible only in the case when the
vertex u2m+1 is adjacent to x and there exist vertices vj , vj+1 adjacent to x. To complete the proof
of (iii) it suffices to consider the path {v2, . . . , v2m+1} and to deduce that v1 is adjacent to x.
Lemma 4.2 is proved.
A path {v1, . . . , vl} in the graph G = (V,E) is called premaximal if there exists a vertex
vl+1 ∈ V \U such that the path {v1, . . . , vl, vl+1} is maximal, i.e., has the maximum possible length.
Lemma 4.3. Let G = (V,E) be not completely disconnected and U be a premaximal path. Then
Inf U 6= U.
Proof. Let U = {v1, . . . , vl} and U ′ = {v1, . . . , vl+1} be a maximal path in G. Then D(vl+1) ⊂
⊂ U. Therefore vl+1 ∈ Inf U 6= U.
Lemma 4.4. Let U = {v1, . . . , vl} be a premaximal path in the H-free graph G = (V,E). If
x ∈ V \ U and d(x, U) =
⌈
l
2
⌉
+ 1, then for every vertex y ∈ V \ U such that y 6= x, inequality
d(y, U) ≤
⌈
l
2
⌉
− 1 holds.
Proof. Assume the contrary, let d(y, U) ≥
⌈
l
2
⌉
. Note that by Lemma 4.2 there is a pair of
vertices vj , vj+1 adjacent to x. Then y can not be adjacent to v1, otherwise the path {y, v1, . . . , vj , x,
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
966 B. V. NOVIKOV, L. YU. POLYAKOVA, G. N. ZHOLTKEVICH
vj+1, . . . , vl} is longer than maximal. Similarly y is not adjacent to vl. Hence for the path U ′ =
=
{
v2, . . . , vl−1
}
the inequality d(y, U ′) ≥
⌈
l
2
⌉
=
⌈
l − 2
2
⌉
+ 1 holds. Therefore by Lemma 4.2 we
can find vertices vi, vi+1 adjacent to y. Without loss of generality, we can also suppose, in view of
statements (ii), (iii) of Lemma 4.2, that x is adjacent to v1. Then the path {x, v1, . . . , vi, y, vi+1, . . . vl}
is longer than maximal path, a contradiction.
Lemma 4.4 is proved.
Corollary 4.1. Let U = {v1, . . . , vl} be a premaximal path in the H-free graph G = (V,E) and∣∣Inf U ∣∣ = p. If p− l ≥ 2, then d(Inf U \ U,U) ≤ (p− l)
⌈
l
2
⌉
.
Let U = {v1, . . . , vl} be a path. We put U (j) = U \ {vj}.
Lemma 4.5. Let l ≥ 3 and U = {v1, . . . , vl} be a path in the H- and K4-free graph G =
= (V,E). Let x ∈ V \ U and d(x, U) =
⌈
l
2
⌉
+ 1. If the number of arcs of the subgraph G[U ] does
not exceed
l2
4
+ 1, then there exists a vertex vj for which d
(
vj , U
(j) ∪ {x}
)
≤
⌈
l
2
⌉
.
Proof. Assume the contrary: for every vertex vj the inequality
d
(
vj , U
(j) ∪ {x}
)
≥
⌈
l
2
⌉
+ 1
holds. By hypothesis G[U ∪{x}] contains no more than
l2
4
+
⌈
l
2
⌉
+2 arcs. The assumption implies:
1
2
(l + 1)
(⌈
l
2
⌉
+ 1
)
≤ l2
4
+
⌈
l
2
⌉
+ 2.
Hence for even l we have l ≤ 6 and for odd l we have l ≤ 3. Therefore it is sufficient to consider
the cases l = 3, 4, 6.
Let A be a set of vertices of U which are adjacent to x, and A = U \A.
If l = 3, then d(x, U) =
⌈
3
2
⌉
+ 1 = 3; hence A = U = {v1, v2, v3}. Then the assumption
implies that the graph G is isomorphic to K4; this contradicts the condition.
Let l = 4. Without loss of generality, we can assume that A = {v3} or A = {v4}. Then
v1, v2 ∈ A. Hence v2 and v4 are not adjacent, otherwise, G contains a “bowtie”. By assumption
d
(
v4, U
(4) ∪ {x}
)
≥ 3, i.e., v4 is adjacent to v1 and x, and A = {v3}. Then (v1, v3) 6∈ E, otherwise
the vertices of U ∪ {x} form a “bowtie”. Therefore, d
(
v3, U
(3) ∪ {x}
)
< 3 contrary to assumption.
Let l = 6. Then | A |= 2. Without loss of generality, by Lemma 4.2 we can suppose that x is
adjacent to v1.
First, assume that v6 6∈ A. Since G is H-free, it follows that either A = {v1, v2, v3, v5} or
A = {v1, v3, v4, v5}. According to the assumption d
(
v6, U
(6)
)
= d
(
v6, U
(6) ∪ {x}
)
= 4. Therefore,
as well as for x, there are two variants: the set of vertices adjacent to v6 equals either {v1, v2, v3, v5}
or {v1, v3, v4, v5}. Checking straightforwardly four cases, we get a contradiction. So v6 ∈ A.
Note that the cases A = {v3, v4}, A = {v3, v6} and A = {v5, v6} are impossible, since G is
H-free. We will obtain the contradiction in every of the remaining variants:
Let A = {v2, v3}. Note that (v2, v4), (v3, v5) 6∈ E, since G is H-free. Then assumption implies
that v2 and v3 are adjacent to v6, hence the vertices {v2, v3, v6, v5, x} form a “bowtie”. The case
A = {v4, v5} is similar.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM 967
Let A = {v2, v4}. Note that (v3, v5), (v1, v3) 6∈ E. The assumption implies that v3 is adjacent
to v6, hence, (v4, v6), (v4, v2) 6∈ E and d(v4, U
(4) ∪ {x}) < 4 contrary to the assumption. The case
A = {v3, v5} is similar.
Let A = {v2, v5}. Then (v4, v6), (v1, v6) 6∈ E and the assumption implies that v2 and v3 are
adjacent to v6. Therefore, the vertices {v2, v3, v6, v4, x} form a “bowtie”.
Lemma 4.5 is proved.
Proposition 4.2. Let G be a connected graph, volG = (p, q), and the length of the maximal
path in G does not exceed 2. Then q ≤ p2
4
+ 1.
Proof. Note that the graph G satisfying the condition is isomorphic to Kp for p ≤ 3 or to K1,p−1.
The inequality can be proved by immediate check.
Proposition 4.2 is proved.
Now we are ready to prove Proposition 4.1.
Proof. First, let G = (V,E) be a H- and K4-free graph, volG = (p, q), and the length of
the maximal path in G is greater than 2. Construct a decomposition choosing the pathes without
self-intersections as Vi and taking a premaximal path as the first component V1.
Let volG[Vi] = (li,mi), volG[Inf Vi] = (pi, qi), i = 1, . . . , n. Then p1 > l1 by Lemma 4.3 and
l1 ≥ 3 by assumption.
Use an induction on p.
We consider separately the case n = 1. We omit the indices in the notations, thus, p = p1, q = q1,
l = l1, m = m1.
Let p > l + 1. By the induction assumption m ≤
⌊
l2
4
⌋
+ 1, and by Corollary 4.1 q − m ≤
≤ (p− l)
⌈
l
2
⌉
. Then
p2
4
+ 1− q =
p2
4
+ 1−m− (q −m) ≥ p2
4
+ 1−
⌊
l2
4
⌋
− 1− (p− l)
⌈
l
2
⌉
=
=
p2
4
− l2
4
+
{
l2
4
}
− (p− l)
l
2
− (p− l)
{
− l
2
}
=
=
(p− l)2
4
+
{
l2
4
}
− (p− l)
{
l
2
}
=
(
p− l
2
−
{
l
2
})2
≥ 0. (3)
Let p = l+1. Note that there is a vertex x ∈ Inf V1 such that d
(
x, Inf V1 \{x}
)
≤
⌈
l
2
⌉
. Indeed,
q −m ≤
⌈
l
2
⌉
+ 1 by Lemma 4.2. Therefore the only vertex of the set Inf V1 \ V1 can be taken as x
or, by Lemma 4.5, x can be chosen in V1.
Let volG
[
Inf V1 \ {x}
]
= (l, s). Then q − s ≤
⌈
l
2
⌉
. Again by the induction assumption
s ≤
⌊
l2
4
⌋
+ 1. So we have
p2
4
+ 1− q =
(l + 1)2
4
+ 1− s− (q − s) ≥ (l + 1)2
4
+ 1−
⌊
l2
4
⌋
− 1−
⌈
l
2
⌉
. (4)
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
968 B. V. NOVIKOV, L. YU. POLYAKOVA, G. N. ZHOLTKEVICH
Note that expression (4) is obtained from (3) by substitution p = l + 1, hence, it is nonnegative.
Thus for n = 1 the statement is proved.
Let n ≥ 2. Put
p′ = p− p1 =
n∑
i=2
pi, q′ = q − q1 =
n∑
i=2
qi +
∑
1≤i<j≤n
d(Vi, Vj).
Applying the induction assumption to the subgraph G
[
V1 t
n⊔
j=2
Inf Vj
]
, we have m1 + q′ ≤
≤
⌊
(l1 + p′)2
4
⌋
+ 1. Moreover q1 −m1 ≤ (p1 − l1)
(⌈
l1
2
⌉
+ 1
)
by Lemma 4.2. Then
p2
4
+ 1− q =
(p1 + p′)2
4
+ 1− (m1 + q′)− (q1 −m1) ≥
≥ (p1 + p′)2
4
+ 1− (l1 + p′)2
4
+
{
(l1 + p′)2
4
}
− 1− (q1 −m1) ≥
≥ p21
4
+
(p1 − l1)p
′
2
− l21
4
+
{
(l1 + p′)2
4
}
− (p1 − l1)
(
l1
2
+
{
− l1
2
}
+ 1
)
=
=
(p1 − l1)
2
4
+ (p1 − l1)
(
p′
2
−
{
− l1
2
}
− 1
)
+
{
(l1 + p′)2
4
}
. (5)
Since
{
− l1
2
}
+ 1 ≤ 3
2
it follows that (5) is nonnegative for p′ ≥ 3.
Note that p′ 6= 1. Otherwise n = 2 and the only vertex of Inf V2 is contained, in view of
connectedness of G, in Inf V1; this is impossible. If p′ = 2, then (5) becomes
(p1 − l1)
2
4
− (p1 − l1)
{
− l1
2
}
+
{
(l1 + 2)2
4
}
=
=
(p1 − l1)
2
4
− (p1 − l1)
{
l1
2
}
+
{
l21
4
}
=
(
p1 − l1
2
−
{
l1
2
})2
≥ 0.
Thus we have completed the proof for K4-free graphs.
Now let G with volG = (p, q) be an arbitrary H-free graph, which is not isomorphic to K4.
Use the induction on the number of subgraphs of G isomorphic to K4. If there are no such
subgraphs, then the statement is already proved; therefore, the basis step is verified.
Let F be a subgraph of G isomorphic to K4 and U = {v1, v2, v3, v4} be the set of its vertices.
Let F = G[V \U ] and volF = (l,m). Note that d(x, U) ≤ 1 for every vertex x ∈ V \U, otherwise
G is not H-free.
If l = 1, then p = 5, q = 7; therefore q ≤ p2
4
+ 1.
If F is isomorphic to K4, then d(U, V \U) ≤ 4, because each of the vertices of F is adjacent to
not more than one vertex of F . In this case p = 8, q ≤ 16 <
⌊
64
4
⌋
+ 1.
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
A DECOMPOSITION OF DIRECTED GRAPHS AND THE TURÁN PROBLEM 969
If F is not isomorphic to K4 and l ≥ 2, then applying the induction assumption to F , we have
m ≤ l2
4
+ 1. Since p = l + 4 and q ≤ m+ l + 6, it follows that
p2
4
+ 1− q ≥ (l + 4)2
4
+ 1−m− l − 6 =
(
l2
4
+ 1−m
)
+ (l − 2) ≥ 0,
as required.
Proposition 4.2 is proved.
1. Dokuchaev M., Novikov B., Zholtkevych G. Partial actions and automata // Algebra and Discrete Math. – 2011. – 11,
№ 2. – P. 51 – 63.
2. Aho A. V., Ullman J. D. The theory of parsing, translation, and compiling. Vol. 2. Compiling. – Prentice-Hall, 1973.
3. Bollobas B. Modern graph theory // Grad. Texts Math. – 1998. – 184.
4. West D. B. Introduction to graph theory. – Pearson Education, 2001.
5. Turán P. On an extremal problem in graph theory (in Hungarian) // Mat. Fiz. Lapok. – 1941. – 46. – P. 436 – 452.
6. Eschen E. M., Hoang Ch. T., Spinrad J. P., Sritharan R. On graphs without a C4 or a diamond // Discrete Appl.
Math. – 2011. – 159, № 7. – P. 581 – 587.
Received 11.06.13,
after revision — 06.10.13
ISSN 1027-3190. Укр. мат. журн., 2014, т. 66, № 7
|
| id | umjimathkievua-article-2191 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:20:27Z |
| publishDate | 2014 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/9e/0e418f90a94fb3e89ae8ef4eae46609e.pdf |
| spelling | umjimathkievua-article-21912019-12-05T10:25:58Z Decomposition of Directed Graphs and the Turán Problem Один розклад орієнтованих графів i задача Турана Zholtkevich, G. N. Novikov, B. V. Polyakova, L. Yu. Жолткевич, Г. Н. Новіков, Б. В. Полякова, Л. Ю . We consider vertex decompositions of (di)graphs appearing in the automata theory and establish some properties of these decompositions. These decompositions are applied to the problem of forbidden subgraphs. Розглянуто вершинні декомпозиції (di)графiв, що виникають у теорії автоматів, встановлено деякі їх властивості, а також наведено застосування їх до задачі про заборонені підграфи. Institute of Mathematics, NAS of Ukraine 2014-07-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/2191 Ukrains’kyi Matematychnyi Zhurnal; Vol. 66 No. 7 (2014); 958–969 Український математичний журнал; Том 66 № 7 (2014); 958–969 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/2191/1383 https://umj.imath.kiev.ua/index.php/umj/article/view/2191/1384 Copyright (c) 2014 Zholtkevich G. N.; Novikov B. V.; Polyakova L. Yu. |
| spellingShingle | Zholtkevich, G. N. Novikov, B. V. Polyakova, L. Yu. Жолткевич, Г. Н. Новіков, Б. В. Полякова, Л. Ю . Decomposition of Directed Graphs and the Turán Problem |
| title | Decomposition of Directed Graphs and the Turán Problem |
| title_alt | Один розклад орієнтованих графів i задача Турана |
| title_full | Decomposition of Directed Graphs and the Turán Problem |
| title_fullStr | Decomposition of Directed Graphs and the Turán Problem |
| title_full_unstemmed | Decomposition of Directed Graphs and the Turán Problem |
| title_short | Decomposition of Directed Graphs and the Turán Problem |
| title_sort | decomposition of directed graphs and the turán problem |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/2191 |
| work_keys_str_mv | AT zholtkevichgn decompositionofdirectedgraphsandtheturanproblem AT novikovbv decompositionofdirectedgraphsandtheturanproblem AT polyakovalyu decompositionofdirectedgraphsandtheturanproblem AT žoltkevičgn decompositionofdirectedgraphsandtheturanproblem AT novíkovbv decompositionofdirectedgraphsandtheturanproblem AT polâkovalû decompositionofdirectedgraphsandtheturanproblem AT zholtkevichgn odinrozkladoríêntovanihgrafívizadačaturana AT novikovbv odinrozkladoríêntovanihgrafívizadačaturana AT polyakovalyu odinrozkladoríêntovanihgrafívizadačaturana AT žoltkevičgn odinrozkladoríêntovanihgrafívizadačaturana AT novíkovbv odinrozkladoríêntovanihgrafívizadačaturana AT polâkovalû odinrozkladoríêntovanihgrafívizadačaturana |