Covering all cliques of a graph
From MaRDI portal
Publication:1174130
DOI10.1016/0012-365X(90)90354-KzbMath0744.05040WikidataQ127673832 ScholiaQ127673832MaRDI QIDQ1174130
Publication date: 25 June 1992
Published in: Discrete Mathematics (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items (79)
Total dominating sequences in graphs ⋮ Fibres of width 3 ordered sets ⋮ Subgraph transversal of graphs ⋮ The algorithmic complexity of the minus clique-transversal problem ⋮ Bounds on the game transversal number in hypergraphs ⋮ Bounds on domination parameters in graphs: a brief survey ⋮ The clique-transversal set problem in \(\{\mathrm{claw},K_4\}\)-free planar graphs ⋮ Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths ⋮ On covering all cliques of a chordal graph ⋮ Clique-transversal number of graphs whose clique-graphs are trees ⋮ Covering and independence in triangle structures ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Total domination stable graphs upon edge addition ⋮ An improved upper bound on the total restrained domination number in cubic graphs ⋮ On 2-Colorings of Hypergraphs ⋮ Minimum size transversals in uniform hypergraphs ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Total transversals and total domination in uniform hypergraphs ⋮ On the transversal number of rank \(k\) hypergraphs ⋮ On the transversal number of \(k\)-uniform connected hypergraphs ⋮ Transversals in regular uniform hypergraphs ⋮ The Tuza–Vestergaard Theorem ⋮ On \(\alpha\)-total domination in graphs ⋮ Hypergraphs with large transversal number and with edge sizes at least four ⋮ A note on the Tuza constant \(c_k\) for small \(k\) ⋮ Nordhaus-Gaddum bounds for total domination ⋮ Bounds on the disjunctive total domination number of a tree ⋮ Unnamed Item ⋮ Total domination versus domination in cubic graphs ⋮ Hypergraphs with large domination number and with edge sizes at least three ⋮ A characterization of hypergraphs that achieve equality in the Chvátal-McDiarmid theorem ⋮ Linear hypergraphs with large transversal number and maximum degree two ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ Locating-total domination in claw-free cubic graphs ⋮ Transversals and domination in uniform hypergraphs ⋮ A note on improved upper bounds on the transversal number of hypergraphs ⋮ Equality in a linear Vizing-like relation that relates the size and total domination number of a graph ⋮ Dominating and total dominating partitions in cubic graphs ⋮ On the clique-transversal number in \({(\mathrm{claw},K_4)}\)-free 4-regular graphs ⋮ Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ The clique-transversal set problem in claw-free graphs with degree at most 4 ⋮ Lower bounds on Tuza constants for transversals in linear uniform hypergraphs ⋮ Algorithms for finding clique-transversals of graphs ⋮ Bounds on the clique-transversal number of regular graphs ⋮ The signed maximum-clique transversal number of regular graphs ⋮ Essential upper bounds on the total domination number ⋮ Covering the cliques of a graph with vertices ⋮ Claw-free cubic graphs with clique-transversal number half of their order ⋮ Total forcing versus total domination in cubic graphs ⋮ Distance-hereditary graphs are clique-perfect ⋮ On a conjecture on total domination in claw-free cubic graphs ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree ⋮ Hypergraphs with large transversal number and with edge sizes at least 3 ⋮ Total domination in 2-connected graphs and in graphs with no induced 6-cycles ⋮ A survey of selected recent results on total domination in graphs ⋮ The \(\langle t \rangle \)-property of some classes of graphs ⋮ Graphs with no induced \(C_ 4\) and \(2K_ 2\) ⋮ A new upper bound on the total domination number in graphs with minimum degree six ⋮ On (1,2)-domination in cubic graphs ⋮ Complete-subgraph-transversal-sets problem on bounded treewidth graphs ⋮ Affine planes and transversals in 3-uniform linear hypergraphs ⋮ Distinguishing-transversal in hypergraphs and identifying open codes in cubic graphs ⋮ Total domination in graphs with given girth ⋮ Domination and Total Domination in Hypergraphs ⋮ An upper bound for the transversal numbers of 4-uniform hypergraphs ⋮ Transversal numbers of uniform hypergraphs ⋮ Transversal Game on Hypergraphs and the $\frac{3}{4}$-Conjecture on the Total Domination Game ⋮ Total domination in partitioned graphs ⋮ On the clique-transversal number of chordal graphs ⋮ My Favorite Domination Conjectures in Graph Theory Are Bounded ⋮ On ordered sets without 2-colourings ⋮ The clique-transversal number of a \(\{K_{1, 3}, K_4 \}\)-free 4-regular graph ⋮ Approximation algorithms for clique transversals on some graph classes ⋮ A sharp upper bound for the transversal number of \(k\)-uniform connected hypergraphs with given size ⋮ Bibliography on domination in graphs and some basic definitions of domination parameters ⋮ Clique-transversal sets of line graphs and complements of line graphs ⋮ Hitting all maximal independent sets of a bipartite graph
Cites Work
- On rigid circuit graphs
- Helly-type hypergraphs and Sperner families
- Clique-transversal sets of line graphs and complements of line graphs
- Characterizations of strongly chordal graphs
- Covering the cliques of a graph with vertices
- An upper bound for the transversal numbers of 4-uniform hypergraphs
- Transversal numbers of uniform hypergraphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Covering all cliques of a graph
