Extended star graphs
Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness...
Saved in:
| Published in: | Algebra and Discrete Mathematics |
|---|---|
| Date: | 2016 |
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Published: |
Інститут прикладної математики і механіки НАН України
2016
|
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/155241 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Extended star graphs / M. Gutierrez, S.B. Tondato // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 239–254. — Бібліогр.: 16 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860224924148301824 |
|---|---|
| author | Gutierrez, M. Tondato, S.B. |
| author_facet | Gutierrez, M. Tondato, S.B. |
| citation_txt | Extended star graphs / M. Gutierrez, S.B. Tondato // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 239–254. — Бібліогр.: 16 назв. — англ. |
| collection | DSpace DC |
| container_title | Algebra and Discrete Mathematics |
| description | Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness of the representation. An extended star graph is the intersection graph of a family of subtrees of a tree that has exactly one vertex of degree at least three. An asteroidal triple in a graph is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. Several subclasses of chordal graphs (interval graphs, directed path graphs) have been characterized by forbidden asteroids. In this paper, we define, a subclass of chordal graphs, called extended star graphs, prove a characterization of this class by forbidden asteroids and show open problems.
|
| first_indexed | 2025-12-07T18:19:51Z |
| format | Article |
| fulltext |
Algebra and Discrete Mathematics RESEARCH ARTICLE
Volume 21 (2016). Number 2, pp. 239–254
© Journal “Algebra and Discrete Mathematics”
Extended star graphs
Marisa Gutierrez and Silvia Beatriz Tondato
Communicated by Yu. V. Zhuchok
Abstract. Chordal graphs, which are intersection graph of
subtrees of a tree, can be represented on trees. Some representation of
a chordal graph often reduces the size of the data structure needed to
store the graph, permitting the use of extremely efficient algorithms
that take advantage of the compactness of the representation. An
extended star graph is the intersection graph of a family of subtrees
of a tree that has exactly one vertex of degree at least three. An
asteroidal triple in a graph is a set of three non-adjacent vertices
such that for any two of them there exists a path between them that
does not intersect the neighborhood of the third. Several subclasses
of chordal graphs (interval graphs, directed path graphs) have been
characterized by forbidden asteroids. In this paper, we define, a
subclass of chordal graphs, called extended star graphs, prove a
characterization of this class by forbidden asteroids and show open
problems.
Introduction
A graph is chordal if it contains no cycle of length at least four as an
induced subgraph. A classical result [6] states that a graph is chordal if
and only if it is the (vertex) intersection graph of a family of subtrees
of a tree. Families of subtrees of a tree together with the tree are called
representation of a graph.
Some representation of a chordal graph often reduces the size of
the data structure needed to store the graph, permitting the use of
2010 MSC: 05C75.
Key words and phrases: clique trees, asteroids, extended star graphs.
240 Extended star graphs
extremely efficient algorithms that take advantage of the compactness
of the representation. Since some chordal graphs have many distinct
representations, it is interesting to consider which one is most desirable
under various circumstances, for example minimum diameter [1], minimum
number of leaves [11], [4], and imposing conditions on trees, subtrees and
intersection sizes [15].
The leafage of a chordal graph is the minimum integer ℓ such that the
graph admits a representation whose tree has exactly ℓ leaves [14]. This
number is related with the existence of asteroidal sets [14].
An asteroidal set A in a graph G is a set of non-adjacent vertices such
that for any v ∈ A the vertices of A \ {v} appears in the same connected
component of G \ N [v]. Note that this definition is compatible with the
definition of asteroidal triple already given. The asteroidal number of a
graph G is the maximum integer a such that G admits an asteroidal set
of cardinality a. If G is a chordal graph containing an asteroidal set A of
size k, then in any representation of G, its tree has at least k leaves. Thus
the asteroidal number of a chordal graph is less or equal to its leafage,
and this inequality can be strict [14].
Habib and Stacho [11] found a polynomial algorithm to compute the
leafage of a chordal graph and built a representation of it.
Natural subclass of chordal graphs are path graphs, directed path
graphs, rooted directed path graphs and interval graphs. A graph is a
path graph if it is the intersection graph of a family of subpaths of a tree.
A graph is a directed path graph if it is the intersection graph of a family
of directed subpaths of a directed tree. A graph is a rooted directed path
graph if it is the intersection graph of a family of directed subpaths of a
rooted tree. A graph is an interval graph if it is the intersection graph of
a family of subpaths of a path.
By definition we have the following inclusions between the different
considered classes (and these inclusion are strict):
interval ⊂ rooted directed path ⊂ directed path ⊂ path ⊂ chordal.
Chaplick and Stacho [4] proved that for path graphs there is a rep-
resentation, where the subtrees are paths, that reaches the leafage, and
then it is also true for directed path graphs [5]. However, it is not true
for rooted directed path graphs [9].
Lekkerkerler and Boland [12] proved that a chordal graph is an in-
terval graph if and only if it contains no asteroidal triple. As byproduct,
they found a characterization of interval graphs by forbidden induced
subgraphs.
M. Gutierrez, S. B. Tondato 241
Panda [16] found the characterization of directed path graph by forbid-
den induced subgraphs and then Cameron, Hoáng and Lévêque [3] gave a
characterization of this class in terms of forbidden asteroidal triples.
Lévêque, Maffray and Preissman [13], found the characterization of
path graphs by forbidden induced subgraphs but there is still no nice
characterization in terms of forbidden asteroids for this class.
Characterizing rooted directed path graph by forbidden induced sub-
graphs or forbidden asteroids are open problems. It is certainly too difficult
to characterizing rooted directed path graphs by forbidden induced sub-
graphs as there are too many (families of) graphs to exclude but Cameron,
Hoáng and Lévêque [2] suggest that directed path graphs could be charac-
terized by forbidding some particular type of asteroidal quadruples (a set
of four non-adjacent vertices such that any three of them is an asteroidal
triple). Thus, several subclasses of rooted directed path graphs [10], [8]
have been characterized by forbidden asteroids, and as byproduct it was
found the characterization of them by forbidden induced subgraphs.
Other subclass of chordal graphs is extended star graphs. A graph G
is an extended star if it is the intersection graph of families of subtrees of
a tree which has exactly one vertex of degree at least tree. Clearly this
class is a natural generalization of interval graphs.
By definition we have the following inclusions between the different
considered classes (and these inclusion are strict):
interval ⊂ extended star ⊂ chordal
On the other hand, this class is hereditary, i.e is closed under vertex-
induced subgraphs. It is known that hereditary classes admit a charac-
terization by forbidden induced subgraphs. Characterize extended star
graphs by forbidden induced subgraphs or by forbidden asteroids are open
problems. Also it is an open problem answer if for extended star graph
there is a representation that reaches the leafage.
In this paper we study properties of extended star graphs, and give a
characterization of this class by forbidden asteroids.
The paper is organized as follows: in Section 2, we give some definitions
and background. In Section 3, we prove a characterization of this class by
forbidden asteroids. Finally, in Section 4, we show conclusions and open
problems.
242 Extended star graphs
1. Definitions and background
A clique in a graph G is a set of pairwise adjacent vertices. Let C(G)
be the set of all maximal cliques of G. We denote by Cx the set of the
maximal cliques that contain x.
The neighborhood of a vertex x is the set N(x) of vertices adjacent
to x and the closed neighborhood of x is the set N [x] = {x} ∪ N(x). A
vertex s is simplicial if its closed neighborhood is a maximal clique.
A clique tree T of a graph G is a tree whose vertices are the elements
of C(G) and such that for each vertex x of G, Cx induces a subtree of T ,
which we will denote by Tx.
Note that G is the intersection graph the vertex sets of subtrees
(Tx)x∈V (G). Gavril [6] proved that a graph is chordal if and only if it has
a clique tree. Clique trees are called models of the graph.
It is clear that a graph is an interval graph if it admits a clique tree
T that is a path such that Tx is a subpath of T for every x ∈ V (G).
A natural generalization of interval graphs are extended star graphs. A
graph G is an extended star if there is a model of G that has at most
exactly one vertex of degree at least three, such models are called extended
star models. Clearly, interval graphs is a subclass of extended star graphs.
Split graphs, minimal forbidden induced subgraphs for interval graphs,
and path graphs minimal forbidden induced subgraphs for directed path
graphs are examples of extended star graphs.
Let T be a clique tree. We often use capital letters to denote the
vertices of a clique tree as these vertices correspond to maximal cliques
of G. In order to simplify the notation, we often write Q ∈ T instead
of Q ∈ V (T ), and e ∈ T instead of e ∈ E(T ). If T ′ is a subtree of T ,
then GT ′ denotes the subgraph of G that is induced by the vertices of
∪Q∈V (T ′)Q.
If G is a graph and V ′ ⊆ V (G), then G\V ′ denotes the subgraph of G
induced by V (G)\V ′. If E′ ⊆ E(G), then G−E′ denotes the subgraph of
G induced by E(G) \ E′. If G, G′ are two graphs, then G + G′ denotes the
graph whose vertices are V (G) ∪ V (G′) and the edges are E(G) ∪ E(G′).
Note that if T, T ′ are two trees such that |V (T ) ∩ V (T ′)| = 0, then T + T ′
is a forest.
Let T be a tree. For V ′ ⊆ V (T ), let T [V ′] be the minimal subtree
of T containing V ′. Then for X, Y ∈ V (T ), T [X, Y ] is the subpath of T
between X and Y . Let T [X, Y ) = T [X, Y ] \ Y , T (X, Y ] = T [X, Y ] \ X
and T (X, Y ) = T [X, Y ] \ {X, Y }. Note that some of these paths may be
empty or reduced to a single vertex when X and Y are equal or adjacent.
M. Gutierrez, S. B. Tondato 243
We say that T [X, Y ] is a branch of T if X is a leaf of T and Y is its most
next vertex of degree at least three of T .
For X, Y, Z ∈ V (T ) that are not on the same path in T , T [X, Y, Z]
is the subtree of T that has X, Y, Z, as its leaves. Let T [X, Y, Z) =
T [X, Y, Z]\Z and T (X, Y, Z) = T [X, Y, Z]\{X, Z}.
In a clique tree T , the label of an edge QQ′ of T is defined as lab(QQ′) =
Q ∩ Q′. Observe that the label of an edge of T is a minimal separator
of G.
Let T be a tree, we denote by ln(T ) the number of leaves of T . The
leafage of a chordal graph G is a minimum integer ℓ such that G admits
a model T with ln(T ) = ℓ [14].
In some cases the leafage of a graph decides if a graph is an extended
star as shows the following Lemma.
Lemma 1. Let G be a chordal graph. If l(G) 6 3 then G is an extended
star graph.
Proof. Let T be a model of G that reaches the leafage, i.e ln(T ) = l(G).
Clearly, ln(T ) 6 3. Thus T has at most exactly one vertex of degree three.
Therefore, G is an extended star graph.
An asteroidal triple in a graph G is a set of three non-adjacent vertices
such that for any two of them there exists a path between them that does
not intersect the neighborhood of the third. An asteroidal n-tupla in a
graph G is a set of n non-adjacent vertices such that for any (n − 1) of
them is an asteroidal (n − 1)-tupla.
If G is a chordal graph containing an asteroidal n-tupla, then in any
model T of G, T has at least n leaves. Thus the leafage of G is greater or
equal to n.
In [7] has been proved that for any clique tree that reaches the leafage,
every vertex of degree at least three, and every choice of three branches
incident to it there is an asteroidal triple on these branches. Thus for
extended star graphs we have the same result.
Lemma 2. Let G be an extended star graph and T be an extended star
model of G with minimum number of leaves equal n > 2. Then G has
n(n−1)(n−2)
6 asteroidal triples.
Proof. Let H1, H2, . . . , Hn be the leaves of T and Q be the vertex of
degree at least three in T . Suppose that GT [H1,H2,H3] does not have an
asteroidal triple. Then there is an interval model T ′ of GT [H1,H2,H3]. Clearly
T − (T [H1, Q) + T [H2, Q) + T [H3, Q)) + T ′ is an extended star model of
244 Extended star graphs
G which has less leaves than T , a contradiction. Hence GT [Hi,Hj ,Hk] has
an asteroidal triple for any three different i, j, k ∈ {1, 2 . . . , n}. Therefore
G has n(n−1)(n−2)
6 asteroidal triples.
Lemma 3. Let G be an extended star chordal graph and T be an extended
star model of G with minimum number of leaves equal n > 2. If T has
exactly k leaves whose distance to the vertex of degree at least three is
greater than one then G has at least an asteroidal (n − k) − tuple.
Proof. Let Q be the vertex of degree n of T , H1, . . . , Hk be the leaves
of T at distance greater than one to Q in T , and Hk+1, . . . , Hn be the
other that are incident to the vertex Q. Let ak+1, . . . , an be simplicial
vertices of Hk+1, . . . , Hn respectively. Since ai is a simplicial vertex of G,
N [ai] = Hi for i ∈ {k + 1, . . . , n}. Let T ′ = T [Hk+1, . . . , Hn]. Suppose
that GT ′ \ N [an] is not a connected graph. So there is at least an edge
HiQ in T ′ for some i ∈ {k + 1, . . . n − 1} such that lab(HiQ) ⊂ Hn.
Then T1 = T − HiQ + HiHn is an extended star model of G that has
less leaves than T , a contradiction. Hence GT ′ \ N [ai] is a connected
graph for all i ∈ {k + 1, . . . , n}. Therefore ak+1, . . . , an is an asteroidal
(n − k)-tupla.
Lemma 4. Let s be a simplicial vertex of G, a minimally non extended
star graph. Then
1) s is a vertex of some asteroidal triple;
2) there is a model T of G which has exactly two vertices of degree
at least three Q and Q′. Moreover, there is at least two branches
T [Q′, H ′
i] for i = 1, 2 such that GT [H′
1
,H′
2
,Q] is not an interval graph;
3) there is a model T of G which has exactly two vertices Q, Q′ of degree
at least three, it has at least two branches T [Q′, H ′
i] for i = 1, 2 such
that GT [H′
1
,H′
2
,Q] is not an interval graph, and if T [Hi, Q] are the
branches of T for i ∈ {1, . . . , n} then GT [Hi,Hj ,Q′] are not interval
graphs for i, j ∈ {1, . . . , n}, i 6= j.
Proof. 1), 2) Since G is a minimal non extended star graph each simplical
vertex of G verifies that if we remove this vertex, the graph obtained has
lower number of maximal cliques than G. Let s be a simplicial vertex
of G. Clearly, there is a maximal clique Q′ 6= N [s] such that N(s) ⊂ Q′.
Since G is a minimal non extended star graph, G \ s is an extended star
graph. By Lemma 1 l(G) > 4, and since s is a simplicial vertex it follows
that l(G \ s) > 3. Let T ′ be an extended star model of G \ s, and Q be the
vertex of degree at least three of T ′. Clearly T = T ′ + N [s]Q′ is a model
M. Gutierrez, S. B. Tondato 245
of G, and since G is not an extended star graph so Q′ 6= Q and Q′ is not
a leaf of T ′. Observe that T has only two vertices of degree at least three
Q and Q′. Let H 6= N [s] be the leaf of T such that Q′ ∈ T [Q, H]. In case
that GT [Q,N [s],H] is an interval graph, there is an interval model T ′
1 of
GT [Q,N [s],H]. Let T1 = T − T (Q, N [s], H] + T ′
1. Clearly T1 is an extended
star model of G, a contradiction. Hence GT [Q,N [s],H] is not an interval
graph, so there is an asteroidal triple, and clearly s must be a vertex of it.
3) Among all the trees in the condition 2), choice that has minimum
leafage, and maximum degree in Q′ (recall that Q′ is a vertex of degree at
least three such that there is at least two branches T [H ′
i, Q′] for i = 1, 2
such that GT [H′
1
,H′
2
,Q] is not an interval graph). If for some i, j ∈ {1, . . . n},
i 6= j, GT [Hi,Hj ,Q′] is an interval graph then there is an interval model T1
of GT [Hi,Hj ,Q′]. Let T ′ = T − T [Hi, Hj , Q′) + T1. Clearly T ′ is a model of
G which has exactly two vertices of degree at least three, a leaf is incident
to Q′ and GT [Q,N [s],H] is not an interval graph. Moreover, if Q′ is a leaf of
T1 then in T ′ the degree of Q′ is the same that in T but ln(T ′) < ln(T ), a
contradiction. If Q′ is not a leaf of T1 then ln(T ′) = ln(T ) but the degree
of Q′ in T ′ is greater than the degree of Q′ in T , a contradiction. Hence
for i, j ∈ {1, . . . n}, i 6= j, GT [Hi,Hj ,Q′] is not an interval graph.
The following algorithm is a technical tool necessary in the proof of
characterization of extended star graph by forbidden asteroids.
Algorithm
Input: A model T that has minimum number of leaves, exactly two
vertices Q, Q′ of degree at least three at distance greater than one, Q∗ ∈
T (Q, Q′) and T [Hi, Q] the branches incident to Q for i ∈ {1, . . . , n}.
Output: A model T ′ that has exactly two vertices Q∗, Q′ of degree
at least three whose distance in T ′ is the same that its distance in T , and
Q, Q∗, Q′ appear in this order in T ′; or it has at least two vertices Q, Q′ of
degree at least three and at most three vertices Q, Q′, Q∗ of degree at least
three, Q, Q∗, Q′ appear in this order in T ′, and there are two branches
T ′[H l, Q] and T ′[Hl+2, Q] for l ∈ {1, . . . , n − 2} such that G
T ′[Hl,Hl+2,Q∗]
is not an interval graph.
If GT [H1,H2,Q∗] is not an interval graph Then
RETURN: T ′ = T
Else
Take T1 an interval model of GT [H1,H2,Q∗] and build a model T 1 =
T − T [H1, H2, Q∗) + T1.
If n = 2 Then
RETURN: T ′ = T 1
246 Extended star graphs
Else
Let T 1[H1, Q] and T 1[Hi, Q] be the branches incident to Q for i ∈
{3, . . . , n}.
If G
T 1[H1,H3,Q∗] is not an interval graph Then
RETURN: T ′ = T 1
Else
i = 2
∗ Take Ti an interval model of G
T i−1[Hi−1,Hi+1,Q∗] and build a model
T i = T i−1 − T i−1[H i−1, Hi+1, Q∗) + Ti.
If n > i + 1 Then
Let T i[H i, Q] and T i[Hj , Q] be the branches incident to Q for j ∈
{i + 2, . . . , n}
If G
T i[Hi,Hi+2,Q∗] is not an interval graph Then
RETURN: T ′ = T i
Else
i = i + 1 go to ∗
Else
RETURN: T ′ = T i
Observe that Ti is an interval model that does not have Q∗ as a leaf,
otherwise ln(T i) < ln(T ) a contradiction since T is a model of G that
has minimum number of leaves.
Note that the way T i was built assure that has at most three vertices
of degree at least three Q, Q∗, Q′ that appear in this order in T i, and
T i[H i, Q], T i[Hj , Q] are the branches of T i for j ∈ {i + 2, . . . , n}. Also
the degree in Ti of Q is n + 1 − i and the degree of Q∗ is i + 2.
We will see that the algorithm works.
Suppose that the algorithm stopped since GT [H1,H2,Q∗] is not an in-
terval graph then T ′ = T has exactly two vertices Q, Q′ of degree at least
three whose distance in T ′ is the same that its distance in T .
Suppose that the algorithm stopped when i = 1 and n = 2. Since T has
minimum number of leaves then Q∗ is not a leaf of T1 then ln(T 1) = ln(T ).
Also T ′ = T 1 has exactly two vertices Q∗, Q′ of degree at least three whose
distance in T ′ is the same that its distance in T , and Q, Q∗, Q′ appear in
this order in T ′. If n > 2 and G
T 1[H1,H3,Q∗] is not an interval graph then
T ′ = T 1 has three vertices Q, Q′, Q∗ of degree at least three, Q, Q∗, Q′
appear in this order in T ′, and there are two branches T ′[H l, Q] and
T ′[Hl+2, Q] for l ∈ {1, . . . , n − 2} such that G
T ′[Hl,Hl+2,Q∗] is not an
interval graph.
M. Gutierrez, S. B. Tondato 247
Suppose that the algorithm stopped when 2 6 i < n − 1. Thus T ′
has three vertices Q, Q′, Q∗ of degree at least three; Q, Q∗, Q′ appear in
this order in T ′, and there are two branches T ′[H l, Q] and T ′[Hl+2, Q] for
l ∈ {1, . . . , n − 2} such that G
T ′[Hl,Hl+2,Q∗] is not an interval graph.
Suppose that the algorithm stopped when i = n − 1. Thus T ′ has
exactly two vertices Q∗, Q′ of degree at least three whose distance in T ′ is
the same that its distance in T , and Q, Q∗, Q′ appear in this order in T ′
2. Forbidden asteroids characterization for extended star
graphs
A pair of asteroidal triples in a graph G is strongly linked if it contains
from two asteroidal triples a1, a2, a3; b1, b2, b3 satisfying the following
conditions:
1) |{a1, a2, a3} ∩ {b1, b2, b3}| 6 1.
2) Every path between ai and bj has vertices in N [a3] and in N [b3] for
i, j ∈ {1, 2}.
3) Let S, M be minimal separators of G with S ⊂ N [b3] and M ⊂ N [a3].
If a1, a2 are in different connected components of G \ S and b1, b2
are in different connected components of G \ M then there is no
Q ∈ C(G) such that M ∪ S ⊂ Q.
Observe that if T is a model of a graph G that has a pair of strongly
linked asteroidal triples a1, a2, a3; b1, b2, b3 and Qi, Q′
i ∈ C(G) such that
ai ∈ Qi and bi ∈ Q′
i for i = 1, 2 then by 2, there are at least two edges
e, e′ ∈ T [Qi, Q′
i] such that lab(e) ⊂ N [a3] and lab(e′) ⊂ N [b3]. Also
Tai
∩ Tbj
= ∅ for i, j ∈ {1, 2}.
Notice that if G has a pair of strongly linked asteroidal triples by
item 2 of the definition: ai, bj are in different connected component of
G \ N [a3] and G \ N [b3] or ai ∈ N [b3] or bj ∈ N [a3] for i, j ∈ {1, 2}.
Theorem 1. Let G be a chordal graph. G is an extended star graph if
and only if G does not have a pair of strongly linked asteroidal triples.
Proof. ⇒ Suppose that G has a pair of strongly linked asteroidal triples
a1, a2, a3 ; b1, b2, b3, and it is an extended star graph. Then there is an
extended star model T of G. Since G has an asteroidal triple then l(G) > 3.
Let Q be the vertex of degree at least three in T . Since T is an extended
star model, Tai
and Tbi
induce paths in T for i ∈ {1, 2, 3}. Let H1, H2, H3
be leaves of T such that Tai
induces a path in T (Q, Hi] for i ∈ {1, 2, 3}.
In the follows, we prove that Tbi
does not induce a path in T (Q, Hj ]
for i, j ∈ {1, 2}.
248 Extended star graphs
Suppose that Tb1
induces a path in T (Q, H1].
Let Ta1
= T [Q1, Q2] and Tb1
= T [Q3, Q4] be such that Q1 ∈ T [Q, Q2]
and Q3 ∈ T [Q, Q4]. Since a1, a2, a3; b1, b2, b3 is a pair of strongly linked
asteroidal triples it follows that Ta1
∩Tb1
= ∅. Thus Q, Q3, Q4, Q1, Q2, H1
or Q, Q1, Q2, Q3, Q4, H1 appear in this order in T [Q, H1].
In case that Q, Q3, Q4, Q1, Q2, H1 appear in this order in T [Q, H1], by
the item 2) of the definition of a pair of strongly linked asteroidal triples,
there is an edge e ∈ T [Q4, Q1] such that lab(e) ⊂ N [a3] so each path
between a1 and a2 in G has neighbors of a3 contradicting that a1, a2, a3
is an asteroidal triple.
In case that Q, Q1, Q2, Q3, Q4, H1 appear in this order in T [Q, H1], by
the item 2) of the definition of a pair of strongly linked asteroidal triples,
there is an edge e′ ∈ T [Q3, Q2] such that lab(e′) ⊂ N [b3]. Then each path
between b1 and b2 in G has neighbors of b3 contradicting that b1, b2, b3 is
an asteroidal triple.
Following the earlier argument, we can conclude that Tbi
does not
induce a path in T (Q, Hj ] for i, j ∈ {1, 2}.
Finally, we prove that Tb3
does not induce a path in T (Q, H3].
Suppose that Tb3
induces a path in T (Q, H3]. Let Ta3
= T [Q5, Q6]
and Tb3
= T [Q7, Q8] be such that Q5 ∈ T [Q, Q6] and Q7 ∈ T [Q, Q8].
Observe that Ta3
∩ Tb3
may be different from ∅. Clearly Q, Q5, Q7, H3 or
Q, Q7, Q5, H3 appear in this order in T [Q, H3]. As Tbi
does not induce
a path in T (Q, Hj ] for i, j ∈ {1, 2}, and Tb3
induces a path in T (Q, H3]
then there exist H4, H5 leaves of T such that Tb1
and Tb2
induce paths
in T (Q, H4] and T (Q, H5] respectively.
In case that Q, Q5, Q7, H3 appear in this order in T [Q, H3], there is
an edge e′ ∈ T [Q1, Q] such that lab(e′) ⊂ N [b3]. By the position in T of
Q5, lab(e′) ⊂ N [a3] so each path between a1 and a2 in G has neighbors
of a3 contradicting that a1, a2, a3 is an asteroidal triple.
In case that Q, Q7, Q5, H3 appear in this order in T [Q, H3], there is an
edge e ∈ T [Q3, Q] such that lab(e) ⊂ N [a3], following the earlier argument
each path between b1 and b2 in G has neighbors of b3 contradicting that
b1, b2, b3 is an asteroidal triple.
Hence Tb3
does not induce a path in T (Q, H3].
By before exposed, Tbi
does not induce a path in T (Q, Hj ] for i, j ∈
{1, 2} and Tb3
does not induce a path in T (Q, H3].
Suppose that Tb1
does not induce a path in T (Q, Hj ] for j ∈ {1, 2, 3}.
Let H4 be a leaf different from H1, H2, H3 such that Tb1
induces a
path in T (Q, H4]. We can assume that Tb3
does not induce a path in
T [H1, Q]. By the item 2) of the definition of a pair of strongly linked
M. Gutierrez, S. B. Tondato 249
asteroidal triples, there are edges e, e′, e ∈ T [H1, Q] and e′ ∈ T [Q, H4]
such that lab(e) ⊂ N [b3] and lab(e′) ⊂ N [a3]. Let S = lab(e) and M =
lab(e′). Clearly S and M are minimal separators of G such that a1, a2
are in different connected components of G \ S, and b1, b2 are in different
connected components of G \ M . By the position in T of the maximal
cliques N [b3] and N [a3] it follows that S ∪ M ⊂ Q, contradicting the
item 3) of the definition of a pair of strongly linked asteroidal triples.
Thus the pair of strongly linked asteroidal triples do not have way of
being located on an extended star model. Therefore, G is not an extended
star graph.
⇐ Suppose that G is a minimally non extended star graph. By Lemma
1, l(G) > 4 and by Lemma 4. 3), there is a model T of G that has exactly
two vertices Q, Q′ of degree at least three. Let H1, . . . , Hn be the leaves of
T such that T [Hi, Q] are branches of T for i = 1, . . . , n, and let H ′
1, . . . , H ′
m
be the leaves of T such that T [H ′
j , Q′] are branches of T for j = 1, . . . , m.
Moreover, by Lemma 4. 3), Q′ has maximum degree and there are at
least two leaves H ′
k, H ′
l for k 6= l, k, l ∈ {1, . . . , m} such that GT [H′
k
,H′
l
,Q]
is not an interval graph. Also for all i 6= j, i, j ∈ {1, . . . , n} GT [Hi,Hj ,Q′]
are not interval graphs. Recall that T has minimum leafage. Among all
the trees in these conditions choice one that minimizing the distance in
T between Q and Q′.
• In case that the distance in T between Q and Q′ is greater than
one we analyze two situations:
Case 1. Applying the Algorithm to T considering Q∗ ∈ T (Q, Q′), and
the branches T [Hi, Q] for i = 1, . . . , n it outputs T ; or Applying the
Algorithm to T considering Q∗ ∈ T (Q, Q′), and the branches T [H ′
j , Q′]
for j = 1, . . . , m it outputs T .
Case 2. Applying the Algorithm to T considering Q∗ ∈ T (Q, Q′), and
the branches T [Hi, Q] for i = 1, . . . , n, and applying the Algorithm to
T considering Q∗ ∈ T (Q, Q′), and the branches T [H ′
j , Q′] for j = 1, . . . , m,
in both cases it does not output T .
Observe that applying the Algorithm to T considering Q∗ ∈ T (Q, Q′),
the branches T [Hi, Q] for i = 1, . . . , n, and by our election of T , which
minimizing the distance in T between Q and Q′, if the Algorithm outputs
a tree with exactly two vertices of degree at least three then it must be T .
More clearly, if it outputs a tree T ′ with exactly two vertices of degree
at least three, which are not Q and Q′, then they must be Q∗ and Q′.
Also by the way T ′ was built l(T ′) = ln(T ), and the distance between
Q∗ and Q′ in T ′ is the same that its distance in T , and it is lower that
250 Extended star graphs
the distance in T between Q and Q′, contradicting this way the election
of T that has exactly two vertices of degree at least three to minimum
distance.
Case 1. Applying the Algorithm to T considering Q∗ ∈ T (Q, Q′), and
the branches T [Hi, Q] for i = 1, . . . , n it outputs T ; or applying the
Algorithm to T considering Q∗ ∈ T (Q, Q′), and the branches T [H ′
j , Q′]
for j = 1, . . . , m it outputs T .
Suppose that applying the Algorithm to T considering Q∗ ∈ T (Q, Q′),
and the branches T [Hi, Q] for i = 1, . . . , n, it outputs T . In this case we
can assume that GT [H1,H2,Q∗] is not an interval graph. We will analyze
two situations: applying the Algorithm considering Q∗ ∈ T (Q, Q′), and
the branches T [H ′
j , Q′] for j = 1, . . . , m it outputs T or not.
Case 1.1. Suppose that applying the Algorithm to T considering Q∗ ∈
T (Q, Q′), and the branches T [Hi, Q] for i = 1, . . . , n it outputs T . Also
suppose that applying the Algorithm to T considering Q∗ ∈ T (Q, Q′) and
the branches T [H ′
j , Q′] for j = 1, . . . , m it outputs T . In this case we can
assume that GT [H′
1
,H′
2
,Q∗] is not an interval graph.
Since GT [H1,H2,Q∗] is not an interval graph then there is an asteroidal
triple a1, a2, a3. Analogously, there is an asteroidal triple b1, b2, b3 in
GT [H′
1
,H′
2
,Q∗].
Suppose that a3 ∈ Q3 with Q3 ∈ T (Q, Q∗], and b3 ∈ Q′
3 with Q′
3 ∈
T [Q∗, Q′). Thus |{a1, a2, a3} ∩ {b1, b2, b3}| 6 1. Then the item 1) of the
definition of a pair of strongly linked asteroidal triples was checked.
Given that Q3, Q′
3 ∈ T (Q, Q′) each path between ai and bj must have
vertices in Q3 and Q′
3 for i, j ∈ {1, 2}. So each path between ai and bj has
neighbors of a3 and b3 for i, j ∈ {1, 2}. Then the item 2) of the definition
of a pair of strongly linked asteroidal triples was checked.
Finally, by our choice of a1, a2, a3; b1, b2, b3, there are not minimal sep-
arators S ⊂ N [b3], M ⊂ N [a3] satisfying a1, a2 are in different connected
components of G \ S and b1, b2 are in different connected components of
G\M . Therefore a1, a2, a3; b1, b2, b3 are a pair of strongly linked asteroidal
triples.
Case 1.2. Suppose that applying the Algorithm to T considering Q∗ ∈
T (Q, Q′), and the branches T [Hi, Q] for i = 1, . . . , n it outputs T . Let T0
be the connected component of T − T (Q∗, Q′) that contains Q and Q∗.
Also, assume that applying the Algorithm to T considering Q∗ ∈
T (Q, Q′) and the branches T [H ′
j , Q′] for j = 1, . . . , m it does not output
T . Let T ′ be the tree outputs by the Algorithm, and T0 be the connected
component of T ′ − T ′(Q, Q∗) that contains Q′ and Q∗.
M. Gutierrez, S. B. Tondato 251
Let T ′′ = T0 + T0. Clearly T ′′ is a model of G.
By the way T ′′ was built Q, Q∗, Q′ appear in this order in T ′′, T ′′
has three vertices Q, Q∗, Q′ of degree at least three. Also there are
four branches in T ′′, T ′′[H1, Q] = T0[H1, Q] = T [H1, Q], T ′′[H2, Q] =
T0[H2, Q] = T [H2, Q], T ′′[H ′
j , Q′] = T0[H ′
j , Q′] = T ′[H ′
j , Q′], T ′′[H ′
l , Q′] =
T0[H ′
l , Q′] = T ′[H ′
l , Q′] for j 6= l, j, l ∈ {1, . . . , m} such that GT ′′[H1,H2,Q∗]
and G
T ′′[H′
j
,H′
l
,Q∗]
are not interval graphs. Suppose that j = 1 and l = 2.
In each situations describing before, we can assume that there is an
asteroidal triple a1, a2, a3 in GT ′′[H1,H2,Q∗] and there is an asteroidal triple
b1, b2, b3 in G
T ′′[H′
1
,H′
2
,Q∗]
. Suppose that a3 ∈ Q3 with Q3 ∈ T ′′(Q, Q∗],
and b3 ∈ Q′
3 with Q′
3 ∈ T ′′[Q∗, Q′). Thus |{a1, a2, a3} ∩ {b1, b2, b3}| 6 1.
Then the item 1) of the definition of a pair of strongly linked asteroidal
triples was checked.
Given that Q3, Q′
3 ∈ T ′′(Q, Q′) each path between ai and bj must
have vertices in Q3 and Q′
3 for i, j ∈ {1, 2}. So each path between ai and
bj has neighbors of a3 and b3 for i, j ∈ {1, 2}. Then the item 2) of the
definition of a pair of strongly linked asteroidal triples was checked.
Finally, by our choice of a1, a2, a3; b1, b2, b3, there are not minimal sep-
arators S ⊂ N [b3], M ⊂ N [a3] satisfying a1, a2 are in different connected
components of G \ S and b1, b2 are in different connected components of
G\M . Therefore a1, a2, a3; b1, b2, b3 are a pair of strongly linked asteroidal
triples.
Case 2. Applying the Algorithm to T considering Q∗ ∈ T (Q, Q′), and
the branches T [Hi, Q] for i = 1, . . . , n and applying the Algorithm to T
considering Q∗ ∈ T (Q, Q′), and the branches T [Hj , Q′] for i = j, . . . , m,
in both cases it does not output T . Let T ′ and T ′ be the subtrees obtained
respectively. By our assumption T ′ 6= T and T ′ 6= T .
Let T0 be the connected component of T ′ − T ′(Q∗, Q′) that contains
Q and Q∗, and T0 be the connected component of T ′ − T ′(Q, Q∗) that
contains Q′ and Q∗. Let T ′′ = T0 + T0.Clearly T ′′ is a model of G.
By the way T ′′ was built Q, Q∗, Q′ appear in this order in T ′′, T ′′ has
at least two vertices Q, Q′ of degree at least three and at most three ver-
tices Q, Q∗, Q′ of degree at least three. Also there are four branches in T ′′,
T ′′[Hi, Q] = T0[Hi, Q] = T ′[Hi, Q], T ′′[Hk, Q] = T0[Hk, Q] = T ′[Hk, Q],
T ′′[H ′
j , Q′] = T0[H ′
j , Q′] = T ′[H ′
j , Q′], T ′′[H ′
l , Q′] = T0[H ′
l , Q′]=T ′[H ′
l , Q′]
for i 6= k, j 6= l, i, k ∈ {1, . . . , n} and j, l ∈ {1, . . . , m} such that
G
T ′′[Hi,Hk,Q∗] and G
T ′′[H′
j
,H′
l
,Q∗]
are not interval graphs. Suppose that
i = 1, k = 2, j = 1 and l = 2.
252 Extended star graphs
We can assume that there is an asteroidal triple a1, a2, a3 of
G
T ′′[H1,H2,Q∗] and there is an asteroidal triple b1, b2, b3 of
G
T ′′[H′
1
,H′
2
,Q∗]
. Suppose that a3 ∈ Q3 with Q3 ∈ T ′′(Q, Q∗], and b3 ∈ Q′
3
with Q′
3 ∈ T ′′[Q∗, Q′). Thus |{a1, a2, a3} ∩ {b1, b2, b3}| 6 1. Then the
item 1) of the definition of a pair of strongly linked asteroidal triples was
checked.
Given that Q3, Q′
3 ∈ T ′′(Q, Q′) each path between ai and bj must
have vertices in Q3 and Q′
3 for i, j ∈ {1, 2}. So each path between ai and
bj has neighbors of a3 and b3 for i, j ∈ {1, 2}. Then the item 2) of the
definition of a pair of strongly linked asteroidal triples was checked.
Finally, by our choice of a1, a2, a3; b1, b2, b3, there are not minimal sep-
arators S ⊂ N [b3], M ⊂ N [a3] satisfying a1, a2 are in different connected
components of G \ S and b1, b2 are in different connected components of
G\M . Therefore a1, a2, a3; b1, b2, b3 are a pair of strongly linked asteroidal
triples.
• In case that the distance in T between Q and Q′ is one.
By our election of T , we can assume that there is an asteroidal
triple a1, a2, a3 of GT [H1,H2,Q′] and there is an asteroidal triple b1, b2, b3 of
GT [H′
1
,H′
2
,Q]. Clearly a3 ∈ Q′ and b3 ∈ Q. It is easy to verify that a1, a2, a3;
b1, b2, b3 satisfy the items 1), 2) of the definition of a pair of strongly
linked asteroidal triples.
Finally, we check the item 3) of the definition of a pair of strongly
asteroidal triples. Let Q1, Q2 ∈ T [H1, H2] be such that minimizing the
distance to Q and ai ∈ Qi for i = 1, 2. Observe that each minimal
separator S ⊂ N [b3], which satisfies a1, a2 are in different connected
components of G \ S, is the label of an edge in T [H1, H2]. Moreover it
is in T [Q1, Q2]. Analogously, each minimal separator M ⊂ N [a3], which
satisfies b1, b2 are in different connected components of G \ M , is the label
of an edge in T [H3, H4], and it is in T [Q3, Q4] with Q3, Q4 ∈ T [H ′
1, H ′
2]
minimizing the distance to Q and bi ∈ Qi+2 for i ∈ {1, 2}. Suppose
that there is Q∗ such that S ∪ M ⊂ Q∗. Let T1, T2 be subtrees of T
such that T1 + T2 + T [Q, Q′] = T , T1 ∩ T2 = ∅, T1 ∩ T [Q, Q′] = {Q},
T2 ∩ T [Q, Q′] = {Q′}. Suppose that Q∗ ∈ T1.It is clear that Q∗, Q, Q′
appear in this order in T . Since M ⊂ N [a3], there is an edge e′ ∈ T2 such
that lab(e′) = M ⊂ Q∗. Given that e′ ∈ T [Q3, Q4] and by the order in
that appear Q∗, Q in T it follows that lab(e′) ⊂ Q. As b3 ∈ Q, Q ⊂ N [b3].
It follows that lab(e′) ⊂ N [b3]. Thus each path between b1 and b2 in G
has vertices in N [b3] contradicting that b1, b2, b3 is an asteroidal triple of
G. Hence Q∗ /∈ T1. Suppose that Q∗ ∈ T2. Following an argument similar
M. Gutierrez, S. B. Tondato 253
to the previous one, we arrive to a contradiction since a1, a2, a3 is an
asteroidal triple of G.
Hence there is no Q∗ ⊃ S ∪ M . Therefore a1, a2, a3; b1, b2, b3 is a pair
of strongly linked asteroidal triples.
Corollary 1. Let G be a minimal non extended star graph. Then l(G) = 4
Proof. Suppose that l(G) > 4. Thus each model of G has at least five
leaves. As a consequence of the proof of Theorem 1, there are a model T
of G and H1, H2, H3, H4 four leaves of T such that GT [H1,H2,H3,H4] 6= G
has a pair of strongly linked asteroidal triples contradicting that G is a
minimal non extended star graph.
Conclusions
The characterization of interval graphs given by Lekkerkerker-Boland,
related chordal non interval graphs with asteroidal triples. This kind of
characterization is given by Cameron, Hoáng and Lévêque for chordal non
directed path graphs. In this paper we have defined a subclass of chordal
graphs, extended star graphs, and we related chordal non extended star
graphs with asteroids. For this purpose we defined a particular type of
asteroidal triple to obtain a characterization of this class by forbidden
asteroids. On the other hand, this class is hereditary so it admits a
characterization by forbidden induced subgraphs. Our result is useful to
build forbidden induced subgraphs, it may be choice two forbidden induced
subgraphs for interval graphs whose asteroidal triples are a1, a2, a3 and
b1, b2, b3 and add a path between a3 and b3 or identify a3 and b3.
On the other hand, it is known that for path graphs and directed path
graphs there is a model that reaches the leafage. But it is not true for
rooted directed path graphs. An interesting questions is if for extended
star graphs there is a model that reaches the leafage or if it is possible to
build a model with minimum number of leaves.
References
[1] J. R. S. Blairk, B. W. Peyton, On finding minimum-diameter clique trees, Nordic
Journal of Computing 1, 1994, pp. 173–201.
[2] K. Cameron, C. T. Hoáng, B. Lévêque, Asteroids in rooted and directed path graphs,
Electronic Notes in Discrete Mathematics 32, 2009, pp.67—74.
[3] K. Cameron, C. T. Hoáng, B. Lévêque, Characterizing directed path graphs by
forbidden asteroids, Journal of Graph Theory 68, 2011, pp.103–112.
254 Extended star graphs
[4] S. Chaplick, J. Stacho, The vertex leafage of chordal graphs, Discrete Applied
Mathematics 168, 2014, pp.14–25.
[5] S. Chaplick, M. Gutierrez, B. Lévêque, S. B. Tondato, From path graphs to directed
path graphs, WG’10, Lecture Notes in Computer Science 6410, 2010, pp.256–265.
[6] F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal
graphs. J. Combin. Theory B 16 47–56 (1974).
[7] M. Gutierrez, J. L. Szwarcfiter, S. B. Tondato, Clique trees of chordal graphs:
leafage and 3-asteroidals, Electronic Notes in Discrete Mathematics 30, 2008,
pp.237–242.
[8] M. Gutierrez, S. B. Tondato, Special asteroidal quadruple on directed path graph non
rooted path graph, Electronic Notes in Discrete Mathematics 44, 2013, pp.47–52.
[9] M. Gutierrez, S. B. Tondato, On models of directed path graphs non rooted directed
path graphs, Graphs and Combinatorics, In press.
[10] M. Gutierrez, S. B. Tondato, Forbidden subgraph characterization of extended star
directed path graphs that are not rooted directed path graphs, Submitted 2015.
[11] M. Habib, J. Stacho, Polynomial-time algorithm for the leafage of chordal graphs,
In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757, 2009,
pp.290–300.
[12] C.G. Lekkerkerker, J. Ch. Boland, Representation of finite graph by a set of
intervals on the real line, Fundamenta Mathematicae Li, 1962, pp.45–64.
[13] B. Lévêque, F. Maffray, M. Preissmann, Characterizing path graphs by forbidden
induced subgraphs, Journal of Graph Theory 62, 2009, pp.369–384.
[14] I. Lin, T. McKee and D. B. West, The leafage of a chordal graphs, Discussiones
Mathematicae Graph Theory 18, 1998, pp.23–48.
[15] C. Monma, V. Wei, Intersection graphs of paths in a tree, J. Combin. Theory B
41, 1986, pp. 141–181.
[16] B.S. Panda, The forbidden subgraph characterization of directed vertex graphs,
Discrete Mathematics 196, 1999, pp.239–256.
Contact information
M. Gutierrez,
S. B. Tondato
Departamento de Matemática, Facultad de Cien-
cias Exactas, Universidad Nacional de La Plata,
50 y 115 La Plata CP 1900, Argentina
E-Mail(s): marisa@mate.unlp.edu.ar,
tondato@mate.unlp.edu.ar
Web-page(s): www.mate.unlp.edu.ar
Received by the editors: 24.09.2015
and in final form 14.02.2016.
|
| id | nasplib_isofts_kiev_ua-123456789-155241 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1726-3255 |
| language | English |
| last_indexed | 2025-12-07T18:19:51Z |
| publishDate | 2016 |
| publisher | Інститут прикладної математики і механіки НАН України |
| record_format | dspace |
| spelling | Gutierrez, M. Tondato, S.B. 2019-06-16T14:33:45Z 2019-06-16T14:33:45Z 2016 Extended star graphs / M. Gutierrez, S.B. Tondato // Algebra and Discrete Mathematics. — 2016. — Vol. 21, № 2. — С. 239–254. — Бібліогр.: 16 назв. — англ. 1726-3255 2010 MSC:05C75. https://nasplib.isofts.kiev.ua/handle/123456789/155241 Chordal graphs, which are intersection graph of subtrees of a tree, can be represented on trees. Some representation of a chordal graph often reduces the size of the data structure needed to store the graph, permitting the use of extremely efficient algorithms that take advantage of the compactness of the representation. An extended star graph is the intersection graph of a family of subtrees of a tree that has exactly one vertex of degree at least three. An asteroidal triple in a graph is a set of three non-adjacent vertices such that for any two of them there exists a path between them that does not intersect the neighborhood of the third. Several subclasses of chordal graphs (interval graphs, directed path graphs) have been characterized by forbidden asteroids. In this paper, we define, a subclass of chordal graphs, called extended star graphs, prove a characterization of this class by forbidden asteroids and show open problems. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Extended star graphs Article published earlier |
| spellingShingle | Extended star graphs Gutierrez, M. Tondato, S.B. |
| title | Extended star graphs |
| title_full | Extended star graphs |
| title_fullStr | Extended star graphs |
| title_full_unstemmed | Extended star graphs |
| title_short | Extended star graphs |
| title_sort | extended star graphs |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/155241 |
| work_keys_str_mv | AT gutierrezm extendedstargraphs AT tondatosb extendedstargraphs |