Degree sequence index strategy
From MaRDI portal
Abstract: We introduce a procedure, called the Degree Sequence Index Strategy (DSI), by which to bound graph invariants by certain indices in the ordered degree sequence. As an illustration of the DSI strategy, we show how it can be used to give new upper and lower bounds on the -independence and the -domination numbers. These include, among other things, a double generalization of the annihilation number, a recently introduced upper bound on the independence number. Next, we use the DSI strategy in conjunction with planarity, to generalize some results of Caro and Roddity about independence number in planar graphs. Lastly, for claw-free and -free graphs, we use DSI to generalize some results of Faudree, Gould, Jacobson, Lesniak and Lindquester.
Recommendations
- scientific article; zbMATH DE number 2544
- On the independence number in \(K_{1,r+1}\)-free graphs
- Bounded-degree independent sets in planar graphs
- Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
- New approach to the \(k\)-independence number of a graph
Cited in
(8)- Domination parameters with number 2: interrelations and algorithmic consequences
- The Slater and sub-\(k\)-domination number of a graph with applications to domination and \(k\)-domination
- A note on the annihilation number and 2-domination number of a tree
- On \(k\)-domination and \(j\)-independence in graphs
- On the k-residue of disjoint unions of graphs with applications to k-independence
- Upper bounds on the \(k\)-forcing number of a graph
- Conjectures of TxGraffiti: independence, domination, and matchings
- Comparing the p-independence number of regular graphs to the q-independence number of their line graphs
This page was built for publication: Degree sequence index strategy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2876022)
