On graphs having maximal independent sets of exactly t distinct cardinalities

DOI10.1007/S00373-012-1132-8MaRDI QIDQ2376089zbMATH OpenOpenAlexFDO

Authors Douglas F. Rall, Bert L. Hartnell

Publication date 26 June 2013

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1110.4310

zbMATH Keywords

cyclegirthmaximal independent set

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Paths and cycles (05C38)

Abstract: For a given positive integer t we consider graphs having maximal independent sets of precisely t distinct cardinalities and restrict our attention to those that have no vertices of degree one. In the situation when t is four or larger and the length of the shortest cycle is at least 6t-6, we completely characterize such graphs.

Recommendations

• On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
• Maximal and maximum independent sets in graphs with at mostr cycles
• A finiteness theorem for maximal independent sets
• Maximal independent sets in graphs with at mostr cycles
• scientific article; zbMATH DE number 5995277

Cites work

• scientific article; zbMATH DE number 1472192 (Why is no real title available?)
• scientific article; zbMATH DE number 3892971 (Why is no real title available?)
• A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets
• A characterization of well covered graphs of girth 5 or greater
• Some covering concepts in graphs
• The effect of vertex and edge deletion on the number of sizes of maximal independent sets

Cited in

(11)

• Arithmetically maximal independent sets in infinite graphs
• On graphs admitting two disjoint maximum independent sets
• On maximal det-independent (res-independent) sets in graphs
• Mind the independence gap
• On unique independent sets in graphs
• scientific article; zbMATH DE number 1472192 (Why is no real title available?)
• Graphs with degree sets of maximal cardinality: a handshaking problem revisited
• Distinct sizes of maximal independent sets on graphs with restricted girth
• On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7
• Maximum independent sets in a proper monograph determined through a signature
• The effect of vertex and edge deletion on the number of sizes of maximal independent sets

This page was built for publication: On graphs having maximal independent sets of exactly \(t\) distinct cardinalities

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