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.
Let $ G_1 \square G_2 $ be the Cartesian product of simple, connected and finite graphs $ G_1 $ and $ G_2 $. We give necessary and sufficient conditions for the Cartesian product of graphs to be very ...strongly perfect. Further, we introduce and characterize the co-strongly perfect graph. The very strongly perfect graph is implemented in the real-time application of a wireless sensor network to optimize the set of master nodes to communicate and control nodes placed in the field.
SUPER STRONGLY PERFECTNESS OF SOME GRAPHS Jothi, R.M.J.; Amutha, A.
International journal of pure and applied mathematics : IJPAM,
10/2013, Volume:
87, Issue:
6
Journal Article
An Acyclic SSP Structure of Grid Graphs Jeya Jothi, R. Mary
2023 First International Conference on Advances in Electrical, Electronics and Computational Intelligence (ICAEECI),
2023-Oct.-19
Conference Proceeding
A Super Strongly Perfect Graph (SSPG) is a graph in which every H (induced subgraph) of G has a dominating set of cardinality (minimal) that cut all cliques (maximal) of H. Here, it is examined the ...grid graphs and its super strongly perfect ness. And it is obstinated the diameter, domination, co - domination numbers of grid graphs.
Wireless sensor network comprises of dense sensor nodes which are randomly deployed. Major challenges in WSN are limited battery source and computation capacity. Considerable research has been ...carried out in the area of maximizing battery lifetime by reducing the energy consumption. Once such proposed technique involves hierarchical topology control. Conventionally proposed algorithm for hierarchical topology control involves computationally intensive soft computing tools. It leads to higher energy consumption in the sink node. Hence it necessitates computationally less intensive technique for cluster head selection. In this paper, an efficient cluster head selection is proposed using minimal dominating set in Super Strongly Perfect (SSP) graph.
A set
S
of pairwise nonadjacent vertices in an undirected graph
G
is called a
stable transversal of
G
if
S
meets every maximal (with respect to set-inclusion) clique of
G
.
G
is called
strongly ...perfect if all its induced subgraphs (including
G
itself) have stable transversals. A
claw is a graph consisting of vertices
a
,
b
,
c
,
d
and edges
ab
,
ac
,
ad
. We characterize claw-free strongly perfect graphs by five infinite families of forbidden induced subgraphs. This result—whose validity had been conjectured by Ravindra Research problems, Discrete Math. 80 (1990) 105–107—subsumes the characterization of strongly perfect line-graphs that was discovered earlier by Ravindra Strongly perfect line graphs and total graphs, Finite and Infinite Sets. Colloq. Math. Soc. János Bolyai 37 (1981) 621–633.
A graph G is super strongly perfect if every induced subgraph H of G possesses a minimal dominating set that meets all the maximal cliques of H. A regular graph is a graph where each vertex has the ...same number of neighbors; i.e. every vertex has the same degree. A regular graph with vertices of degree k is called a k-regular graph. Regularity of graphs plays an important role in communication networks. Super strongly perfect graph's structure includes even cycles (which is 2 - regular). In this line of thought, a discussion on the regularity of complete k-partite graph is given using super strongly perfect graph.
A Graph G is Super Strongly Perfect Graph if every induced sub graph H of G possesses a minimal dominating set that meets all the maximal complete sub graphs of H. In this paper we have characterized ...the structure of super strongly perfect graphs in Prism and Rook's Networks. Along with this characterization, we have investigated the Super Strongly Perfect ness in Prism and Rook's Networks. Also we have given the relationship between diameter, domination and co-domination numbers of Prism Network.
A graph is strongly perfect if every induced subgraph H has a stable set that meets every nonempty maximal clique of H. The characterization of strongly perfect graphs by a set of forbidden induced ...subgraphs is not known. Here we provide several new minimal non-strongly-perfect graphs.
PDF
