Equistable simplicial, very well-covered, and line graphs

DOI10.1016/J.DAM.2013.01.022MaRDI QIDQ2448905zbMATH OpenOpenAlexFDO

Authors Vadim E. Levit, Martin Milanič

Publication date 5 May 2014

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

Full work available at URL https://doi.org/10.1016/j.dam.2013.01.022

zbMATH Keywords

line graphequistable graphgeneral partition graphtriangle conditiontriangle graphpolynomial time algorithmvery well-covered graphsimplicial graphstrongly equistable graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Recommendations

• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• Equistarable bipartite graphs
• Equistable graphs
• Equistable chordal graphs

Cites work

• scientific article; zbMATH DE number 4139799 (Why is no real title available?)
• scientific article; zbMATH DE number 4025485 (Why is no real title available?)
• scientific article; zbMATH DE number 4068928 (Why is no real title available?)
• scientific article; zbMATH DE number 4093496 (Why is no real title available?)
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 4123780 (Why is no real title available?)
• scientific article; zbMATH DE number 1076150 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A Survey of the Algorithmic Properties of Simplicial, Upper Bound and Middle Graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A characterization and hereditary properties for partition graphs
• A class of threshold and domishold graphs: Equistable and equidominating graphs
• Algorithmic graph theory and perfect graphs
• Complexity results for equistable graphs and related classes
• Efficiency of a Good But Not Linear Set Union Algorithm
• Equistable chordal graphs
• Equistable distance-hereditary graphs
• Equistable graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• Equistable series-parallel graphs
• Fast Algorithms for Maximum Subset Matching and All-Pairs Shortest Paths in Graphs with a (Not So) Small Vertex Cover
• Faster scaling algorithms for general graph matching problems
• Graph Classes: A Survey
• Graph-Theoretic Concepts in Computer Science
• Independent Domination in Triangle Graphs
• On the complexity of the independent set problem in triangle graphs
• Quasi-threshold graphs
• Randomly matchable graphs
• Recent examples in the theory of partition graphs
• Some covering concepts in graphs
• Threshold graphs and related topics
• Trivially perfect graphs
• Very well covered graphs

Cited in

(13)

• Short proofs on the structure of general partition, equistable and triangle graphs
• Strong cliques and equistability of EPT graphs
• Equistarable bipartite graphs
• On equistable, split, CIS, and related classes of graphs
• Detecting strong cliques
• Equistable series-parallel graphs
• Recognizing k-equistable graphs in FPT time
• Equistarable graphs and counterexamples to three conjectures on equistable graphs
• Structural results for general partition, equistable and triangle graphs
• Equistable graphs, general partition graphs, triangle graphs, and graph products
• Equiangular lines and covers of the complete graph
• Decomposing 1-Sperner hypergraphs
• scientific article; zbMATH DE number 1525371 (Why is no real title available?)

This page was built for publication: Equistable simplicial, very well-covered, and line graphs

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