Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree

DOI10.1007/S00373-020-02244-YMaRDI QIDQ2657095zbMATH OpenOpenAlexFDO

Authors Suil O, Yongtang Shi, Zhenyu Taoqiu

Publication date 17 March 2021

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

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

zbMATH Keywords

\(k\)-distance chromatic number\(k\)-independence numberchromatic numberindependence numberregular graphs

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Connectivity (05C40) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: The $k$-independence number of a graph $G$ is the maximum size of a set of vertices at pairwise distance greater than $k$. In this paper, for each positive integer $k$, we prove sharp upper bounds for the $k$-independence number in an $n$-vertex connected graph with given minimum and maximum degree.

Recommendations

• Spectral bounds for the \(k\)-independence number of a graph
• The \(k\)-independence number of \(t\)-connected graphs
• Graphs with given k-independence number
• New approach to the \(k\)-independence number of a graph
• On the \(k\)-independence number of graphs

Cites work

• Broadcast chromatic numbers of graphs
• Computing \(k\)-independent sets for regular bipartite graphs
• scientific article; zbMATH DE number 5158519 (Why is no real title available?)
• scientific article; zbMATH DE number 637355 (Why is no real title available?)
• Independence and average distance in graphs
• On the injective chromatic number of graphs
• Spectral bounds for the \(k\)-independence number of a graph
• The Chromatic Number of Graph Powers
• The strong chromatic index ofC4-free graphs

Cited in

(26)

• On local and global independence numbers of a graph
• Bounds for the independence number in \(k\)-step Hamiltonian graphs
• On the independence number in \(K_{1,r+1}\)-free graphs
• New approach to the \(k\)-independence number of a graph
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Toughness and normalized Laplacian eigenvalues of graphs
• A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number
• The \(k\)-independence number of \(t\)-connected graphs
• On the \(k\)-independence number of graphs
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• On \(k\)-independence in graphs with emphasis on trees
• On inertia and ratio type bounds for the k-independence number of a graph and their relationship
• Eigenvalues of \(K_{1,k}\)-free graphs and the connectivity of their independence complexes
• On the k-residue of disjoint unions of graphs with applications to k-independence
• Graphs with given k-independence number
• Spectral bounds for the \(k\)-independence number of a graph
• On the stability of the graph independence number
• Highly connected subgraphs of graphs with given independence number (extended abstract)
• A lower bound on the \(k\)-conversion number of graphs of maximum degree \(k+1\)
• The optimal bound on the 3-independence number obtainable from a polynomial-type method
• On trees with given diameter and extremal number of distance-k independent sets
• Independence number in graphs and its upper bounds
• Algebraic bounds for the independence and chromatic number of graph powers
• On the independence number of graph powers
• On the k-independence number of graph products
• Evaluating a permutation of the power and complement operations of a graph with respect to its independence numbers

This page was built for publication: Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree

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