×

Eccentric counts, connectivity and chordality. (English) Zbl 1259.05053

Summary: Let \(e_{j}\) denote the number of vertices of eccentricity \(j\) in a graph. We provide sharp lower bounds on \(e_{j}\) in graphs of given connectivity and in chordal graphs of given connectivity.

MSC:

05C12 Distance in graphs
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brandstädt, A.; Le, V. B.; Spinrad, J. P., Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), SIAM: SIAM Philadelphia, PA · Zbl 0919.05001
[2] Chang, G. J., Centers of chordal graphs, Graphs Combin., 7, 305-313 (1991) · Zbl 0763.05053
[3] Chepoĭ, V. D., Centers of triangulated graphs, Math. Notes, 43, 82-86 (1988) · Zbl 0698.05059
[4] Chepoi, V. D.; Dragan, F. F.; Yan, C., Additive sparse spanners for graphs with bounded length of largest induced cycle, Theoret. Comput. Sci., 347, 54-75 (2005) · Zbl 1080.68085
[5] Ferrero, D.; Harary, F., On eccentricity sequences of connected graphs, AKCE Int. J. Graphs Comb., 6, 401-408 (2009) · Zbl 1210.05031
[6] Hrnčiar, P.; Monoszová, G., Minimal eccentric sequences with two values, Acta Univ. M. Belii Ser. Math., 12, 43-65 (2005) · Zbl 1182.05051
[7] Lesniak-Foster, L. M., Eccentric sequences in graphs, Period. Math. Hungar., 6, 287-293 (1975) · Zbl 0363.05053
[8] Mubayi, D.; West, D. B., On the number of vertices with specified eccentricity, Graphs Combin., 16, 441-452 (2000) · Zbl 0988.05036
[9] Yushmanov, S. V., A simple relationship between the diameter and the radius of a graph, Moscow Univ. Math. Bull., 43, 46-48 (1988) · Zbl 0676.05050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.