Characterizations of strongly chordal graphs

DOI10.1016/0012-365X(83)90154-1zbMATH Open0514.05048MaRDI QIDQ1051004FDOQ1051004

Publication date: 1983

Published in: Discrete Mathematics (Search for Journal in Brave)

chordal graphs polynomial algorithms forbidden induced subgraph characterization independent domination totally balanced hypergraphs minimum weight domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Structural characterization of families of graphs (05C75)

Cites Work

Title not available (Why is that?)
On rigid circuit graphs
The intersection graphs of subtrees in trees are exactly the chordal graphs
Parallel concepts in graph theory
Triangulated graphs and the elimination process
Domination, independent domination, and duality in strongly chordal graphs
Totally-Balanced and Greedy Matrices
The k-Domination and k-Stability Problems on Sun-Free Chordal Graphs
Title not available (Why is that?)
Hypergraphs with no special cycles
Properties of (0,1)-matrices with no triangles

Cited In (only showing first 100 items - show all)

Algorithmic aspects of clique-transversal and clique-independent sets
Representation characterizations of chordal bipartite graphs
Totally-Balanced and Greedy Matrices
String graphs of \(k\)-bend paths on a grid
Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph
Weighted maximum-clique transversal sets of graphs
Labeling algorithms for domination problems in sun-free chordal graphs
Characterizing and computing the structure of clique intersections in strongly chordal graphs
On the computational difficulty of the terminal connection problem
A characterization of totally balanced hypergraphs
On probe permutation graphs
The domatic number problem on some perfect graph families
Boxicity of leaf powers
Chordal bipartite graphs with high boxicity
Chordal bipartite completion of colored graphs
Diameter determination on restricted graph families
On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs
Enumerating minimal connected dominating sets in graphs of bounded chordality
Simplicial powers of graphs
Regular codes in regular graphs are difficult
Bibliography on domination in graphs and some basic definitions of domination parameters
Recognizing interval digraphs and interval bigraphs in polynomial time
Covering all cliques of a graph
On hypergraph acyclicity and graph chordality
A characterization of strongly chordal graphs
An approximation algorithm for clustering graphs with dominating diametral path
Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
\(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs
The recognition of geodetically connected graphs
Solving the all-pairs-shortest-length problem on chordal bipartite graphs
On basic chordal graphs and some of its subclasses
\(L(2,1)\)-labeling of perfect elimination bipartite graphs
The algorithmic complexity of mixed domination in graphs
Domination, independent domination, and duality in strongly chordal graphs
A linear time algorithm for finding all hinge vertices of a permutation graph
Domination in convex and chordal bipartite graphs
Induced matchings
A good characterization of squares of strongly chordal split graphs
Clique graphs and Helly graphs
Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
The algorithmic use of hypertree structure and maximum neighbourhood orderings
Arboricity, \(h\)-index, and dynamic algorithms
Tree spanners on chordal graphs: complexity and algorithms
On edge perfectness and classes of bipartite graphs
Recognizing Helly edge-path-tree graphs and their clique graphs
On minimal vertex separators of dually chordal graphs: properties and characterizations
Algorithms for maximum matching and minimum fill-in on chordal bipartite graphs
Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs
HAMILTONian circuits in chordal bipartite graphs
The maximum vertex coverage problem on bipartite graphs
Variations of maximum-clique transversal sets on graphs
Biconvex graphs: Ordering and algorithms
Doubly lexical ordering of dense 0--1 matrices
Algorithmic aspects of the generalized clique-transversal problem on chordal graphs
Characterizing width two for variants of treewidth
On recognition of threshold tolerance graphs and their complements
All-pairs-shortest-length on strongly chordal graphs
Ptolemaic Graphs and Interval Graphs Are Leaf Powers
Algorithmic aspects of \(k\)-tuple total domination in graphs
Simplicial Powers of Graphs
Graph modification problem for some classes of graphs
On distance-3 matchings and induced matchings
A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
A decomposition strategy for the vertex cover problem
Strongly chordal and chordal bipartite graphs are sandwich monotone
Structure and linear time recognition of 3-leaf powers
Standard graded vertex cover algebras, cycles and leaves
Rooted directed path graphs are leaf powers
Convexity in Graphs and Hypergraphs
Crown-free lattices and their related graphs
On the dominating set polytope
On the Steiner, geodetic and hull numbers of graphs
Block duplicate graphs and a hierarchy of chordal graphs
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
Additive sparse spanners for graphs with bounded length of largest induced cycle
Classes of bipartite graphs related to chordal graphs
A note on sparseness conditions on chordless vertices of cycles
On balanced graphs
Neighborhood subtree tolerance graphs
On Injective Colourings of Chordal Graphs
The price of connectivity for cycle transversals
Graphs whose neighborhoods have no special cycles
On the complexity of variations of mixed domination on graphs
Dominating cliques in chordal graphs
Minimal elimination ordering for graphs of bounded degree
Requiring chords in cycles
Monge and feasibility sequences in general flow problems
Cycle Extendability of Hamiltonian Strongly Chordal Graphs
One-sided discrete terrain guarding and chordal graphs
On the terminal connection problem
Broadcast domination and multipacking in strongly chordal graphs
Perfect circular arc coloring
The domatic number of block-cactus graphs
Odd twists on strongly chordal graphs
The parallel complexity of elimination ordering procedures
Efficient \((j, k)\)-dominating functions
Recognizing threshold tolerance graphs in \(O(n^2)\) time
A survey on pairwise compatibility graphs
Counting perfect matchings and the switch chain
An approximation result for the interval coloring problem on claw-free chordal graphs

This page was built for publication: Characterizations of strongly chordal graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1051004)