✦ LIBER ✦

The rank of a graph after vertex addition

✍ Scribed by Jean H. Bevis; Kevin K. Blount; George J. Davis; Gayla S. Domke; Valerie A. Miller

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 471 KB
Volume: 265
Category: Article
ISSN: 0024-3795
DOI: 10.1016/s0024-3795(96)00513-7

No coin nor oath required. For personal study only.

✦ Synopsis

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, since the number of edges that can be added with this vertex is variable. The rank of the new graph cannot decrease and it can increase by at most 2. We obtain results examining several cases of vertex addition.

📜 SIMILAR VOLUMES

On vertex ranking of a starlike graph

✍ Sun-yuan Hsieh 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 76 KB

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)-ran

Non rank 3 strongly regular graphs with

Non rank 3 strongly regular graphs with the 5-vertex condition

✍ A. V. Ivanov 📂 Article 📅 1989 🏛 Springer-Verlag 🌐 English ⚖ 361 KB

Vertex-transitive graphs that remain con

Vertex-transitive graphs that remain connected after failure of a vertex and its neighbors

✍ Y. O. Hamidoune; A. Lladó; S. C. López 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 148 KB

A d-regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex and its neighbors will be called vosperian. Let be a vertex-transitive graph of

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.

Vertex-Compressed Subalgebras of a Graph

Vertex-Compressed Subalgebras of a Graph von

✍ Ilwoo Cho 📂 Article 📅 2008 🏛 Springer Netherlands 🌐 English ⚖ 741 KB

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.