Can I read Removable Edges in a K-connected Graph and a Construction Method for K-connected Graphs on EtoBox?

Removable Edges in a K-connected Graph and a Construction Method for K-connected Graphs by Jianji Su; Xiaofeng Guo; Liqiong Xu is a Computer Science article available to read on EtoBox.

What is Removable Edges in a K-connected Graph and a Construction Method for K-connected Graphs about?

An edge e of a k-connected graph G is said to be a removable edge if G e is still k-connected, where G e denotes the graph obtained from G by deleting e to get Ge and, for any end vertex of e with degree k -1 in Ge, say x, deleting x and then adding edges between any pair of non-adjacent vertices in N G-e (x). Xu and Guo [Liqiong Xu, Xiaofeng Guo, Removable edges in a 5-connected graph and a construction method of 5-connected graphs, Discrete Math. 308 (2008Math. 308 ( ) 1726Math. 308 ( -1731] ] proved that a 5-connected graph G has no removable edge if and only if G ∼ = K 6 , using this result, they gave a construction method for 5-connected graphs. A k-connected graph G is said to be a quasi (k + 1)-connected if G has no nontrivial k-vertex cut. Jiang and Su [Hongxing Jiang, Jianji Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193] conjectured that for k ≥ 4 the minimum degree of a minimally quasi k-connected graph is equal to k -1. In the present paper, we prove this conjecture and prove for k ≥ 3 that a k-connected graph G has no removable edge if and only if G is isomorphic to either K k+1 or (when k is even) the graph obtained from

Who reads Removable Edges in a K-connected Graph and a Construction Method for K-connected Graphs?

Author

Jianji Su; Xiaofeng Guo; Liqiong Xu

Publisher

Elsevier Science; Elsevier ; Elsevier BV (ISSN 0012-365X)

Published

2009

Language

EN

Field

Computer Science (Physical Sciences)