On graphs having maximal independent sets of exactly t distinct cardinalities

DOI10.1007/S00373-012-1132-8zbMATH Open1267.05189arXiv1110.4310OpenAlexW2075056990MaRDI QIDQ2376089FDOQ2376089

Bert L. Hartnell, Douglas F. Rall

Publication date: 26 June 2013

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

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.

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

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 Keywords

cyclegirthmaximal independent set

Mathematics Subject Classification ID

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

Cites Work

• A characterization of well covered graphs of girth 5 or greater
• Some covering concepts in graphs
• A characterization of graphs of girth eight or more with exactly two sizes of maximal independent sets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (9)

• On unique independent sets in graphs
• Distinct sizes of maximal independent sets on graphs with restricted girth
• On graphs admitting two disjoint maximum independent sets
• Arithmetically maximal independent sets in infinite graphs
• Graphs with degree sets of maximal cardinality: a handshaking problem revisited
• Mind the independence gap
• Title not available (Why is that?)
• Maximum independent sets in a proper monograph determined through a signature
• On graphs with maximal independent sets of few sizes, minimum degree at least 2, and girth at least 7

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)