Maximizing the number of edges in optimal k-rankings

DOI10.1016/J.AKCEJ.2015.06.005zbMATH Open1333.05109arXiv1702.02060OpenAlexW1096198614MaRDI QIDQ896093FDOQ896093

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

• Title not available (Why is that?)
• 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)