Characterization of Super Strongly Perfect Graphs in Chordal and Strongly Chordal Graphs [PDF]
Mapana - Journal of Sciences, 2012 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 investigated the characterization of Super Strongly Perfect graphs using odd cycles.
R Mary Jeya Jothi, A Amutha
openaire +3 more sources
Strongly chordal and chordal bipartite graphs are sandwich monotone [PDF]
Journal of Combinatorial Optimization, 2009 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Pinar Heggernes +3 more
openaire +4 more sources
Characterizations of strongly chordal graphs [PDF]
Discrete Mathematics, 1983 AbstractIn this paper we present several characterizations of the class of strongly chordal graphs. These include a forbidden induced subgraph characterization and two characterizations in terms of totally balanced matrices. Another characterization yields a polynomial recognition algorithm.Interest in these graphs arises in several ways.
Farber, Martin
openaire +2 more sources
The parallel solution of domination problems on chordal and strongly chordal graphs [PDF]
Discrete Applied Mathematics, 1994 This paper discusses the problem of the existence of a dominating clique in a chordal graph. The equivalence of the dominating set problem and the minimum dominating clique problem for strongly chordal graphs has also been proved. Further, it has been proved that both problems are equivalent to the cover problem viz.
Elias Dahlhaus, Peter Damaschke
openaire +2 more sources
A new characterization of strongly chordal graphs [PDF]
Discrete Mathematics, 1999 Define the strength of a set of edges as the number of inclusion-maximal complete subgraphs that contain it. The main result is that a graph is strongly chordal if and only if, for every \(k\geq 1\), every cycle of edges of strength at least \(k\) with no chord of strength at least \(k\) itself has strength at least \(k\).
McKee, Terry A.
openaire +2 more sources
All-pairs-shortest-length on strongly chordal graphs [PDF]
Discrete Applied Mathematics, 1996 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
V. Balachandhran, C. Pandu Rangan
openaire +2 more sources
Exploring Dominating Functions and Their Complexity in Subclasses of Weighted Chordal Graphs and Bipartite Graphs [PDF]
MathematicsDomination problems are fundamental problems in graph theory with diverse applications in optimization, network design, and computational complexity.
Chuan-Min Lee
doaj +2 more sources
Domination, independent domination, and duality in strongly chordal graphs [PDF]
Discrete Applied Mathematics, 1984 Polynomial-time algorithms for finding minimum weight dominating sets and independent dominating sets in strongly chordal graphs are presented in this paper. The algorithms are based on linear programming formulations of the problems and consist of two stages: in the first - a greedy algorithm is used to solve the corresponding dual program, and in the
Farber, Martin, Martin Farber
openaire +2 more sources
Maximum vertex-weighted matching in strongly chordal graphs [PDF]
Discrete Applied Mathematics, 1998 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Manoel B. Campêlo, Sulamita Klein
openaire +2 more sources
Finding Dominating Cliques Efficiently, in Strongly Chordal Graphs and Undirected Path Graphs [PDF]
Discrete Mathematics, 1990 A set of vertices in a graph is called a dominating set if every vertex not in the set is adjacent to at least one vertex in the set. A dominating clique is a dominating set that induces a complete subgraph. The problem of locating a dominating clique of minimum cardinality is known to be NP-complete for general chordal graphs.
Kratsch, Dieter, Dieter Kratsch
openaire +2 more sources