The 2-Ranking Numbers of Graphs

MaRDI QIDQ6275880zbMATH OpenFDO

Authors Jordan Almeter, Samet Demircan, Andrew Kallmeyer, Kevin G. Milans, Robert Winslow

Publication date 24 July 2016

Abstract: In a graph whose vertices are assigned integer ranks, a path is well-ranked if the endpoints have distinct ranks or some interior point has a higher rank than the endpoints. A ranking is an assignment of ranks such that all nontrivial paths are well-ranked. A $k$-ranking is a relaxation in which all nontrivial paths of length at most $k$ are well-ranked. The $k$-ranking number of a graph $G$ is the minimum $t$ such that there is a $k$-ranking of $G$ using ranks in $1,ldots,t$. We prove that the $2$-ranking number of the $n$-dimensional hypercube $Q_n$ is $n+1$. As a corollary, we improve the bounds on the star chromatic number of products of cycles when each cycle has length divisible by $4$. For $mlen$, we show that the $2$-ranking number of $K_{m}mathopsquare{K}_n$ is $Omega(nlogm)$ and $O(n{m}^{lo{g}_2(3)-1})$ with an asymptotic result when $m$ is constant and an exact result when $m!$ divides $n$. We prove that every subcubic graph has $2$-ranking number at most $7$, and we also prove the existence of a graph with maximum degree $k$ and $2$-ranking number $Omega(k^2/log(k))$.

This page was built for publication: The 2-Ranking Numbers of Graphs

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