Characterizations of strongly chordal graphs

From MaRDI portal

Publication:1051004

Jump to:navigation, search

DOI10.1016/0012-365X(83)90154-1zbMath0514.05048MaRDI QIDQ1051004

Martin Farber

Publication date: 1983

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

zbMATH Keywords

polynomial algorithms chordal graphs 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)

Related Items

Doubly lexical ordering of dense 0--1 matrices, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs, Upper maximal graphs of posets, Minimal elimination of planar graphs, Convexity in Graphs and Hypergraphs, Complexity of Hamiltonian cycle reconfiguration, Regular vines with strongly chordal pattern of (conditional) independence, Pairwise Compatibility Graphs: A Survey, Symmetric graph-theoretic roles of two-pairs and chords of cycles, Unit ball graphs on geodesic spaces, Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, Clique-perfectness and balancedness of some graph classes, The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality, Unnamed Item, Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time, Broadcast domination and multipacking in strongly chordal graphs, Beyond Helly graphs: the diameter problem on absolute retracts, On some graph classes related to perfect graphs: a survey, On the computational difficulty of the terminal connection problem, Further results on Hendry's Conjecture, Pairwise compatibility graphs: complete characterization for wheels, MAT-free graphic arrangements and a characterization of strongly chordal graphs by edge-labeling, On the complexity of variations of mixed domination on graphs^†, The parallel complexity of elimination ordering procedures, Dually chordal graphs, On the dominating set polytope, Chordal bipartite completion of colored graphs, Combinatorial Generation via Permutation Languages. V. Acyclic Orientations, Variations of maximum-clique transversal sets on graphs, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, One-sided terrain guarding and chordal graphs, Min-Orderable Digraphs, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Rainbow domination and related problems on strongly chordal graphs, The maximum vertex coverage problem on bipartite graphs, Standard graded vertex cover algebras, cycles and leaves, Tight bounds for online coloring of basic graph classes, Algorithmic aspects of clique-transversal and clique-independent sets, Strongly simplicial vertices of powers of trees, Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium, Algorithms for generating strongly chordal graphs, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Labelled packing functions in graphs, Restricted unimodular chordal graphs, Unnamed Item, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Intersection graphs of non-crossing paths, Representation characterizations of chordal bipartite graphs, Graph parameters, implicit representations and factorial properties, Recognizing Helly edge-path-tree graphs and their clique graphs, Diameter determination on restricted graph families, Signed clique-transversal functions in graphs, The degree-preserving spanning tree problem in strongly chordal and directed path graphs, Minimal elimination ordering for graphs of bounded degree, Maxclique and unit disk characterizations of strongly chordal graphs, Cycle Extendability of Hamiltonian Strongly Chordal Graphs, Ptolemaic Graphs and Interval Graphs Are Leaf Powers, On Injective Colourings of Chordal Graphs, Odd twists on strongly chordal graphs, Hardness and structural results for half-squares of restricted tree convex bipartite graphs, Graphs with unique dominating sets, Semitotal domination: new hardness results and a polynomial-time algorithm for graphs of bounded mim-width, Counting Perfect Matchings and the Switch Chain, String graphs of k-bend paths on a grid, Tight Bounds for Online Coloring of Basic Graph Classes, Oracles for vertex elimination orderings, Requiring chords in cycles, Perfect circular arc coloring, Simplicial Powers of Graphs, Strong Chordality of Graphs with Possible Loops, Hamiltonian Chordal Graphs are not Cycle Extendable, Additive sparse spanners for graphs with bounded length of largest induced cycle, A survey on pairwise compatibility graphs, Semi-dynamic algorithms for strongly chordal graphs, On balanced graphs, On the complexity of \(\{k\}\)-domination and \(k\)-tuple domination in graphs, Efficient \((j, k)\)-dominating functions, Fast Diameter Computation within Split Graphs, Totally-Balanced and Greedy Matrices, Alternating cycle-free matchings, An approximation result for the interval coloring problem on claw-free chordal graphs, A parallel algorithm for computing Steiner trees in strongly chordal graphs, Neighborhood perfect graphs, The parallel solution of domination problems on chordal and strongly chordal graphs, Enumerating minimal connected dominating sets in graphs of bounded chordality, Regular codes in regular graphs are difficult, One-sided discrete terrain guarding and chordal graphs, On the terminal connection problem, An approximation algorithm for clustering graphs with dominating diametral path, Tree spanners on chordal graphs: complexity and algorithms, The recognition of geodetically connected graphs, Solving the all-pairs-shortest-length problem on chordal bipartite graphs, Finding the minimum bandwidth of an interval graph, On basic chordal graphs and some of its subclasses, The weakly connected independent set polytope in corona and join of graphs, Structure and linear time recognition of 3-leaf powers, One-node cutsets and the dominating set polytope, Totally balanced and totally unimodular matrices defined by center location problems, Towards a characterization of leaf powers by clique arrangements, Characterizing width two for variants of treewidth, On recognition of threshold tolerance graphs and their complements, Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs, Graph modification problem for some classes of graphs, On edge perfectness and classes of bipartite graphs, On hypergraph acyclicity and graph chordality, Labeling algorithms for domination problems in sun-free chordal graphs, A note on perfectly orderable graphs, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Recognizing interval digraphs and interval bigraphs in polynomial time, A decomposition strategy for the vertex cover problem, Skew rank decompositions, HAMILTONian circuits in chordal bipartite graphs, All-pairs-shortest-length on strongly chordal graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms, A note on sparseness conditions on chordless vertices of cycles, Finding a sun in building-free graphs, Minimum paired-dominating set in chordal bipartite graphs and perfect elimination bipartite graphs, Matching and multidimensional matching in chordal and strongly chordal graphs, Weighted maximum-clique transversal sets of graphs, Arboricity, \(h\)-index, and dynamic algorithms, A good characterization of squares of strongly chordal split graphs, Subgraph trees in graph theory, \(L(2,1)\)-labeling of dually chordal graphs and strongly orderable graphs, A linear-time algorithm for finding locally connected spanning trees on circular-arc graphs, Total coloring of rooted path graphs, \(L(2,1)\)-labeling of perfect elimination bipartite graphs, Domination in convex and chordal bipartite graphs, Algorithmic aspects of \(k\)-tuple total domination in graphs, Crown-free lattices and their related graphs, Strongly chordal and chordal bipartite graphs are sandwich monotone, Covering all cliques of a graph, Boxicity of leaf powers, Chordal bipartite graphs with high boxicity, Characterizing and computing the structure of clique intersections in strongly chordal graphs, Classes of bipartite graphs related to chordal graphs, Mutual transferability for \((F, B, R)\)-domination on strongly chordal graphs and cactus graphs, A greedy reduction algorithm for setup optimization, Variations of \(Y\)-dominating functions on graphs, A linear time algorithm for finding all hinge vertices of a permutation graph, Computing a perfect edge without vertex elimination ordering of a chordal bipartite graph, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, Monge and feasibility sequences in general flow problems, Strong elimination ordering of the total graph of a tree, The algorithmic complexity of mixed domination in graphs, On minimal vertex separators of dually chordal graphs: properties and characterizations, Rooted directed path graphs are leaf powers, On probe permutation graphs, Signed and minus clique-transversal functions on graphs, Exact leaf powers, On distance-3 matchings and induced matchings, On the Steiner, geodetic and hull numbers of graphs, On the complexity of signed and minus total domination in graphs, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Neighborhood subtree tolerance graphs, The price of connectivity for cycle transversals, From a simple elimination ordering to a strong elimination ordering in linear time, Special eccentric vertices for the class of chordal graphs and related classes, Chromatic numbers of competition graphs, Induced matchings, A min-max relation for the partial q-colourings of a graph. II: Box perfection, Optimisation and hypergraph theory, On forcibly hereditary P-graphical sequences, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, Biconvex graphs: Ordering and algorithms, Simplicial powers of graphs, Totally balanced dissimilarities, The domatic number of block-cactus graphs, Domination, independent domination, and duality in strongly chordal graphs, A characterization of strongly chordal graphs, A new characterization of strongly chordal graphs, Block duplicate graphs and a hierarchy of chordal graphs, Graphs whose neighborhoods have no special cycles, Clique graphs and Helly graphs, The domatic number problem on some perfect graph families, Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs, A characterization of totally balanced hypergraphs, Bibliography on domination in graphs and some basic definitions of domination parameters, Dominating cliques in chordal graphs

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1051004&oldid=13063737"