Leaves and inverse degree of a graph

There are many long-standing conjectures on trees, and many invariants of graphs arose from Graffiti conjectures. Let diam(G) and id(G) = Σ u∈V(G) 1/deg G (u) be the diameter and the inverse degree of a connected graph G, respectively. The notation n d (G) indicates the number of vertices of degree...

Full description

Saved in:
Bibliographic Details
Main Authors: Bing Yao, Xiang-en Chen, Ming Yao, Jiajuan Zhang, Jingxia Guo
Format: Conference Proceeding
Language:English
Subjects:
Biomedical engineering
Educational institutions
Informatics
Information science
Mathematics
Terminology
USA Councils
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:There are many long-standing conjectures on trees, and many invariants of graphs arose from Graffiti conjectures. Let diam(G) and id(G) = Σ u∈V(G) 1/deg G (u) be the diameter and the inverse degree of a connected graph G, respectively. The notation n d (G) indicates the number of vertices of degree d in G. We show that (i) diam(G) + id(G) ≤ 3/2 |G|. (ii) id(G) ≤ 1/2 |G|+1 if G is hamiltonian. (iii) id(G) ≤ n1 (T)+|M|-1/2 for a certain spanning tree T and a largest matching M of G. (iv) For a tree T on n vertices, 2 ≤ 2 · id(T ) - n ≤ n 1 (T), diam(T) + n 1 (T) + 1 ≤ 2 · id(T ), diam(T) + id(T ) ≤ 2n-n 1 (T)-1/2n 2 (T)+1, and 2·id(T ) ≤ 2(n 1 (T )+|M|)-1 for a largest matching M of T.
ISSN:1948-2914
1948-2922
DOI:10.1109/BMEI.2010.5639359