Strong cliques in diamond-free graphs Chiarelli, Nina; Martínez-Barona, Berenice; Milanič, Martin ...
Theoretical computer science,
02/2021, Volume:
858
Journal Article
Peer reviewed
Open access
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of ...diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems all remain NP-hard or co-NP-hard when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following three problems whose computational complexity is open in general can be solved in polynomial time in the class of diamond-free graphs: Does every induced subgraph have a strong clique? Is every maximal clique strong? Is every edge contained in a strong clique? The last two results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
•A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets.•We study strong cliques in the class of diamond-free graphs.•We characterize diamond-free CIS graphs and study their Erdős-Hajnal property.•We characterize co-strongly perfect diamond-free graphs.•We derive hardness results for five related problems.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal ...cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique
C in a vertex‐transitive graph
Γ is strong if and only if
∣
C
∣
∣
I
∣
=
∣
V
(
Γ
)
∣ for every maximal independent set
I of
Γ. On the basis of this result we prove that a vertex‐transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex‐transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5‐valent vertex‐transitive graphs admitting a strong clique. Our results imply that every vertex‐transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex‐transitive CIS graph which is not localizable.
Full text
Available for:
BFBNIB, FZAB, GIS, IJS, KILJ, NLZOH, NUK, OILJ, SBCE, SBMB, UL, UM, UPUK
We consider several graphs classes defined in terms of conditions on cliques and stable sets, including CIS, split, equistable, and other related classes. We pursue a systematic study of the ...relations between them. As part of this study, we introduce two generalizations of CIS graphs, obtain a new characterization of split graphs, and a characterization of CIS line graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
On CIS circulants Boros, Endre; Gurvich, Vladimir; Milanič, Martin
Discrete mathematics,
03/2014, Volume:
318
Journal Article
Peer reviewed
Open access
A circulant is a Cayley graph over a cyclic group. A well-covered graph is a graph in which all maximal stable sets are of the same size α=α(G), or in other words, they are all maximum. A CIS graph ...is a graph in which every maximal stable set and every maximal clique intersect. It is not difficult to show that a circulant G is a CIS graph if and only if G and its complement G¯ are both well-covered and the product α(G)α(G¯) is equal to the number of vertices. It is also easy to demonstrate that both families, the circulants and the CIS graphs, are closed with respect to the operations of taking the complement and the lexicographic product. We study the structure of the CIS circulants. It is well-known that all P4-free graphs are CIS. In this paper, in addition to the simple family of P4-free circulants, we construct a non-trivial sparse but infinite family of CIS circulants. We are not aware of any CIS circulant that could not be obtained from graphs in this family by the operations of taking the complement and the lexicographic product.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Strong Cliques in Diamond-Free Graphs Chiarelli, Nina; Martínez-Barona, Berenice; Milanič, Martin ...
Graph-Theoretic Concepts in Computer Science,
2020, 20201009, Volume:
12301
Book Chapter
Peer reviewed
Open access
A strong clique in a graph is a clique intersecting all inclusion-maximal stable sets. Strong cliques play an important role in the study of perfect graphs. We study strong cliques in the class of ...diamond-free graphs, from both structural and algorithmic points of view. We show that the following five NP-hard or co-NP-hard problems remain intractable when restricted to the class of diamond-free graphs: Is a given clique strong? Does the graph have a strong clique? Is every vertex contained in a strong clique? Given a partition of the vertex set into cliques, is every clique in the partition strong? Can the vertex set be partitioned into strong cliques?
On the positive side, we show that the following two problems whose computational complexity is open in general can be solved in linear time in the class of diamond-free graphs: Is every maximal clique strong? Is every edge contained in a strong clique? These results are derived from a characterization of diamond-free graphs in which every maximal clique is strong, which also implies an improved Erdős-Hajnal property for such graphs.
Full text
Available for:
FIS, FZAB, GEOZS, GIS, IJS, IMTLJ, KILJ, KISLJ, MFDPS, NUK, OBVAL, OILJ, PNG, SAZU, SBCE, SBJE, SBMB, SBNM, UKNU, UL, UM, UPUK, VKSCE, ZAGLJ
Let us consider two binary systems of inequalities (i)
C
x
≥
e
and (ii)
C
x
≤
e
, where
C
∈
{
0
,
1
}
m
×
n
is an
m
×
n
(
0
,
1
)
-matrix,
x
∈
{
0
,
1
}
n
, and
e
is the vector of
m
ones. The set of ...all support-minimal (respectively, support-maximal) solutions
x
to (i) (respectively, to (ii)) is called the
blocker (respectively,
anti-blocker).
A blocker
B
(respectively, anti-blocker
A
) is called
exact if
C
x
=
e
for every
x
∈
B
(respectively,
x
∈
A
).
Exact blockers can be completely characterized. There is a one-to-one correspondence between them and
P
4
-free graphs (along with a well-known one-to-one correspondence between the latter and the so-called read-once Boolean functions). However, the class of exact anti-blockers is wider and more sophisticated. We demonstrate that it is closely related to the so-called CIS graphs, more general
ℓ
-CIS
d
-graphs, and
Δ
-conjecture.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A graph is CIS if every maximal clique interesects every maximal stable set. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We characterize graphs in which ...every maximal matching saturates all vertices of degree at least two and use this result to give a structural, efficiently testable characterization of claw-free CIS graphs. We answer in the negative a question of Dobson, Hujdurović, Milanič, and Verret Vertex-transitive CIS graphs, European J. Combin. 44 (2015) 87–98 asking whether the number of vertices of every CIS graph is bounded from above by the product of its clique and stability numbers. On the positive side, we show that the question of Dobson et al. has an affirmative answer in the case of claw-free graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
PDF
