<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
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 $m\le n$, we show that the $2$-ranking number of $K_m \mathop\square K_n$ is $��(n\log m)$ and $O(nm^{\log_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 $��(k^2/\log(k))$.
FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO)
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |