Diameter-vital edges in a graph

Autor: H. B. Walikar, Fred Buckley, Medha Itagi Huilgol
Rok vydání: 2011
Předmět:
Zdroj: Aequationes mathematicae. 82:201-211
ISSN: 1420-8903
0001-9054
DOI: 10.1007/s00010-011-0087-9
Popis: The graph resulting from contracting edge e is denoted as G/e and the graph resulting from deleting edge e is denoted as G − e. An edge e is diameter-essential if diam(G/e) < diam(G), diameter-increasing if diam(G − e) < diam(G), and diameter-vital if it is both diameter-essential and diameter-increasing. We partition the edges that are not diameter-vital into three categories. In this paper, we study realizability questions relating to the number of edges that are not diameter-vital in the three defined categories. A graph is diameter-vital if all its edges are diameter-vital. We give a structural characterization of diameter-vital graphs.
Databáze: OpenAIRE
Externí odkaz: