On unique independent sets in graphs

DOI10.1016/0012-365X(94)90389-1MaRDI QIDQ1331985zbMATH OpenFDO

Authors Werner Siemes, Jerzy Topp, Lutz Volkmann

Publication date 27 September 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(94)90389-1

zbMATH Keywords

\(k\)-independence\(k\)-independent setcycleextremal graphsunique independent set

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Paths and cycles (05C38) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Review text

For a nonnegative integer \(k\), a subset \(I\) of the vertex set \(V(G)\) of a simple graph \(G\) is said to be \(k\)-independent if \(I\) is independent and every independent subset \(I'\) of \(G\) with \(| I'| \geq | I|- (k- 1)\) is a subset of \(I\). A \(k\)-independent set \(I\) is strong \(k\)-independent if \(V(G)- I\) is independent in \(G\). For \(0\leq \ell \leq k\), \(k\)-independence implies \(\ell\)-independence. A set is 0-independent iff it is an independent set of maximum size; a set is 1-independent iff it is a unique independent set, a concept investigated in [\textit{G. Hopkins} and \textit{W. Staton}, Graphs with unique maximum independent set, Discrete Math. 57, 245-251 (1985; Zbl 0583.05034)]. The authors characterize \(k\)-independent sets for (a) graphs in which every even cycle has a chord, (b) graphs in which every block is a complete graph or an odd cycle, and (c) bipartite graphs. They then generalize results of Hopkins and Staton, and of \textit{F. Harary} and \textit{M. D. Plummer} [On the core of a graph, Proc. Lond. Math. Soc., III. Ser. 17, 305-314 (1967; Zbl 0152.412)] in Theorem 8: For a positive integer \(k\) a tree \(T\) has a strong \(k\)-independent set iff the distance between any two vertices of degree at most \(k\) is even. Finally, they prove a ``Turán-type extremeal theorem for graphs containing a \(k\)-independent set, and provide examples of extremal graphs.

Recommendations

• On \(k\)-independence in graphs with emphasis on trees
• Graphs with unique maximum independent sets
• Trees with the second and third largest number of maximum independent sets.
• Estimates of the number of independent sets in graphs with a fixed independence number
• On graphs having maximal independent sets of exactly \(t\) distinct cardinalities
• Fourier analysis and large independent sets in powers of complete graphs
• Maximal k-independent sets in graphs
• The number of maximum independent sets in graphs
• scientific article; zbMATH DE number 1465674
• A finiteness theorem for maximal independent sets

Cites work

• Graphs with unique maximum independent sets
• scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• On the Core of a Graph^†

Cited in

(10)

• Graphs with unique maximum independent sets
• Graphs with unique minimum edge dominating sets and graphs with unique maximum independent sets of vertices
• On independent cliques and linear complementarity problems
• Unique minimum semipaired dominating sets in trees
• Graphs with a unique maximum independent set up to automorphisms
• Unique irredundance, domination and independent domination in graphs
• scientific article; zbMATH DE number 4132180 (Why is no real title available?)
• On perfect and unique maximum independent sets in graphs.
• On local maximum stable set greedoids
• The number of maximum dissociation sets in trees

This page was built for publication: On unique independent sets in graphs

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