Sharp Upper Bounds on the k -Independence Number in Graphs with Given Minimum and Maximum Degree
- PDF / 1,727,623 Bytes
- 16 Pages / 439.37 x 666.142 pts Page_size
- 39 Downloads / 213 Views
(0123456789().,-volV) (0123456789().,-volV)
ORIGINAL PAPER
Sharp Upper Bounds on the k-Independence Number in Graphs with Given Minimum and Maximum Degree Suil O1 • Yongtang Shi2
•
Zhenyu Taoqiu2
Received: 22 August 2019 / Revised: 28 March 2020 / Accepted: 22 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
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. Keywords k-independence number Independence number Chromatic number k-distance chromatic number Regular graphs
AMS subject classification 2010 05C69
1 Introduction Throughout this paper, all graphs are simple, undirected, and finite. For two vertices u and v in a graph G, we define the distance between u and v, written dG ðu; vÞ or simply d(u, v), to be the length of the shortest path between u and v. For a nonnegative integer k, a k-independent set in a graph G is a vertex set S VðGÞ Suil O: Research supported by NRF-2017R1D1A1B03031758 and by NRF-2018K2A9A2A06020345. Y. Shi, Z. Taoqiu: Research supported by the National Natural Science Foundation of China (No. 11811540390). & Zhenyu Taoqiu [email protected] Suil O [email protected] Yongtang Shi [email protected] 1
Department of Applied Mathematics and Statistics, The State University of New York, Incheon 21985, Korea
2
Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China
123
Graphs and Combinatorics
such that the distance between any two vertices in S is bigger than k. Note that the 0independent set is V(G) and an 1-independent set is an independent set. The kindependence number of a graph G, written ak ðGÞ, is the maximum size of a kindependent set in G. n It is known that a1 ðGÞ ¼ aðGÞ vðGÞ , where vðGÞ and aðGÞ are the chromatic number and independence number of a graph G, repsectively. Similarly, by finding the k-distance chromatic number of G, we can find a lower bound for ak ðGÞ. It will be discussed in Sect. 4. Other graph parameters such as the average distance [4], injective chromatic number [6], packing chromatic number [5], and strong chromatic index [9] are also directly related to the k-independence number. Lower bounds on the corresponding distance or packing chromatic number can be given by finding upper bounds on the k-independence number. Alon and Mohar [2] asked the extremal value for the distance chromatic number in graphs of a given girth and degree. Firby and Haviland [4] proved an upper bound for ak ðGÞ in an n-vertex connected graph. We give a proof of the theorem below, because with a similar idea, we prove Theorem 3.2, which is one of the main results in this paper. Theorem 1.1 ([4]) For a positive integer k, if G is a non-complete n-vertex connected graph with diamðGÞ k þ 1, then 8 2n > > ; if k is even, < kþ2 2 ak ðGÞ 2n 2 > > : ; if k is odd. kþ1 Furthermore
Data Loading...
