Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the independence ratio of distance graphs
189
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph $G$ is the maximum density of an independent set in $G$. Lih, Liu, and Zhu [Star extremal circulant graphs, SIAM J. Discrete Math. 12 (1999) 491--499] showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs. We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three, determine asymptotic values for others, and present several conjectures.
rate research
Read More
We investigate the independence number of two graphs constructed from a polarity of $mathrm{PG}(2,q)$. For the first graph under consideration, the ErdH{o}s-Renyi graph $ER_q$, we provide an improvement on the known lower bounds on its independence number. In the second part of the paper we consider the ErdH{o}s-Renyi hypergraph of triangles $mathcal{H}_q$. We determine the exact magnitude of the independence number of $mathcal{H}_q$, $q$ even. This solves a problem posed by Mubayi and Williford.
For a simple, undirected and connected graph $G$, $D_{alpha}(G) = alpha Tr(G) + (1-alpha) D(G)$ is called the $alpha$-distance matrix of $G$, where $alphain [0,1]$, $D(G)$ is the distance matrix of $G$, and $Tr(G)$ is the vertex transmission diagonal matrix of $G$. Recently, the $alpha$-distance energy of $G$ was defined based on the spectra of $D_{alpha}(G)$. In this paper, we define the $alpha$-distance Estrada index of $G$ in terms of the eigenvalues of $D_{alpha}(G)$. And we give some bounds on the spectral radius of $D_{alpha}(G)$, $alpha$-distance energy and $alpha$-distance Estrada index of $G$.
$H_q(n,d)$ is defined as the graph with vertex set ${mathbb Z}_q^n$ and where two vertices are adjacent if their Hamming distance is at least $d$. The chromatic number of these graphs is presented for various sets of parameters $(q,n,d)$. For the $4$-colorings of the graphs $H_2(n,n-1)$ a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust $4$-colorings of $H_2(n,n-1)$ is presented.
Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexes $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Delta$. Then, every collection of $leftlfloorleft(frac{Delta}{2}+1right)(n-1)rightrfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.
Let $G$ be a simple graph with maximum degree $Delta(G)$ and chromatic index $chi(G)$. A classic result of Vizing indicates that either $chi(G )=Delta(G)$ or $chi(G )=Delta(G)+1$. The graph $G$ is called $Delta$-critical if $G$ is connected, $chi(G )=Delta(G)+1$ and for any $ein E(G)$, $chi(G-e)=Delta(G)$. Let $G$ be an $n$-vertex $Delta$-critical graph. Vizing conjectured that $alpha(G)$, the independence number of $G$, is at most $frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is that $alpha(G)<frac{3n}{5}$. We show that for any given $varepsilonin (0,1)$, there exist positive constants $d_0(varepsilon)$ and $D_0(varepsilon)$ such that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d_0$ and maximum degree at least $D_0$, then $alpha(G)<(frac{{1}}{2}+varepsilon)n$. In particular, we show that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d$ and $Delta(G)ge (d+2)^{5d+10}$, then [ alpha(G) < left. begin{cases} frac{7n}{12}, & text{if $d= 3$; } frac{4n}{7}, & text{if $d= 4$; } frac{d+2+sqrt[3]{(d-1)d}}{2d+4+sqrt[3]{(d-1)d}}n<frac{4n}{7}, & text{if $dge 19$. } end{cases} right. ]
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
