Maximizing the number of edges in optimal k-rankings

DOI10.1016/J.AKCEJ.2015.06.005MaRDI QIDQ896093zbMATH OpenOpenAlexFDO

Authors Rigoberto Flórez, Darren Narayan

Publication date 11 December 2015

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

rankingcoloringmaximum number of edgesminimum \(k\)-ranking

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A $k$-ranking is a vertex $k$-coloring such that if two vertices have the same color any path connecting them contains a vertex of larger color. The rank number of a graph is smallest $k$ such that $G$ has a $k$-ranking. For certain graphs $G$ we consider the maximum number of edges that may be added to $G$ without changing the rank number. Here we investigate the problem for $G=P_{2^{k-1}}$, $C_{2^k}$, $K_{m_1,m_2,dots,m_t}$, and the union of two copies of $K_n$ joined by a single edge. In addition to determining the maximum number of edges that may be added to $G$ without changing the rank number we provide an explicit characterization of which edges change the rank number when added to $G$, and which edges do not.

Recommendations

• scientific article; zbMATH DE number 1743759
• Minimal rankings
• Rank numbers of graphs that are combinations of paths and cycles
• Rankings of Graphs
• Further results on minimal rankings

Cites work

• Minimal k-rankings and the rank number of P^2_n
• Minimal k-rankings for prism graphs
• Minimal rankings
• On a graph partition problem with application to VLSI layout
• On-line ranking number for cycles and paths
• Rank numbers of grid graphs
• Ranking numbers of graphs
• Rankings of Graphs

Cited in

(6)

• scientific article; zbMATH DE number 1743759 (Why is no real title available?)
• Finding the edge ranking number through vertex partitions
• The birank number of operationally constructed graphs
• \(l_p\)-optimal rankings and max-optimal rankings are different
• Optimal edge ranking of complete bipartite graphs in polynomial time
• Edge ranking of graphs is hard

This page was built for publication: Maximizing the number of edges in optimal \(k\)-rankings

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