✦ LIBER ✦

On vertex ranking of a starlike graph

✍ Scribed by Sun-yuan Hsieh

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 76 KB
Volume: 82
Category: Article
ISSN: 0020-0190
DOI: 10.1016/s0020-0190(01)00262-9

No coin nor oath required. For personal study only.

✦ Synopsis

A vertex coloring c : V → {1, 2, . . . , t} of a graph G = (V , E) is a vertex t-ranking if for any two vertices of the same color every path between them contains a vertex of larger color. The vertex ranking number χ r (G) is the smallest value of t such that G has a vertex t-ranking. A χ r (G)-ranking of G is said to be an optimal vertex ranking. In this paper, we present an O(|V | + |E|) time algorithm for finding an optimal vertex ranking of a starlike graph G = (V , E). Our result implies that an optimal vertex ranking of a split graph can be computed in linear time.

📜 SIMILAR VOLUMES

The rank of a graph after vertex additio

The rank of a graph after vertex addition

✍ Jean H. Bevis; Kevin K. Blount; George J. Davis; Gayla S. Domke; Valerie A. Mill 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 471 KB

Let r(G) denote the rank of the adjacency matrix of a graph G. When a vertex and its incident edges are deleted from G, the rank of the resultant graph cannot exceed r(G) and can decrease by at most 2. The problem of determining the exact effect of adding a single vertex to a graph is more difficult

On packing 3-vertex paths in a graph

✍ Atsushi Kaneko; Alexander Kelmans; Tsuyoshi Nishimura 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 276 KB 👁 2 views

On the linear vertex-arboricity of a pla

On the linear vertex-arboricity of a planar graph

✍ K. S. Poh 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 153 KB 👁 2 views

## Abstract We prove in this note that the linear vertex‐arboricity of any planar graph is at most three, which confirms a conjecture due to Broere and Mynhardt, and others.

On a theorem about vertex colorings of g

On a theorem about vertex colorings of graphs

✍ Claudio Bernardi 📂 Article 📅 1987 🏛 Elsevier Science 🌐 English ⚖ 121 KB

Lawrence [2, Theorem 3] and Borodin and Kostochka [1, Lemma 2' 1 both give the same theorem about vertex colorings of graphs (Corollary 1 below). But Lawrence's proof, although powerful, is a little long, and Borodin and Kostoehka state the result without a proof.

A note on vertex pancyclic oriented grap

A note on vertex pancyclic oriented graphs

✍ Bang-Jensen, J�rgen; Guo, Yubao 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 185 KB 👁 2 views

Let D be an oriented graph of order n ≥ 9, minimum degree at least n -2, such that, for the choice of distinct vertices x and y, . Graph Theory 18 (1994), 461-468) proved that D is pancyclic. In this note, we give a short proof, based on Song's result, that D is, in fact, vertex pancyclic. This also

On the intersection rank of a graph

✍ James A. Wiseman 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 748 KB

Wiseman, J.A., On the intersection rank of a graph, Discrete Mathematics 104 293-305.