Minimum Breadth of a Graph

Authors

  • Agnes M Tabitha Research Scholar, Visvesvaraya Technological University, Belgaum, India;
  • Reddy L Sudershan Professor, C M S Business School, Jain University, Bangalore, India;

DOI:

https://doi.org/10.12723/mjs.34.3

Keywords:

Diameter, Radius, Peripheral vertices, Central vertices, Diametral Path, Breadth

Abstract

Breadth of a graph as the maximum of heights taken over all diametral paths is investigated in [3, 4], where height is taken by placing each diametral path on level y = 0 and placing uniquely the rest of the vertices on levels y = 1, 2…k keeping adjacency intact. A parameter minimum breadth is introduced as minimum of heights with respect to all diametral paths. A few results on minimum breadth in certain classes of graphs are presented. Also the bounds on number of vertices and edges for graphs of known diameter and minimum breadth are proposed.

Author Biographies

Agnes M Tabitha, Research Scholar, Visvesvaraya Technological University, Belgaum, India;

Research Scholar, Visvesvaraya Technological University, Belgaum, India;

Reddy L Sudershan, Professor, C M S Business School, Jain University, Bangalore, India;

Professor, C M S Business School, Jain University, Bangalore, India;

References

F. Buckley and F. Harary, Distance in Graphs, Perseus Books, 1990.

F. Harary, Graph Theory, Addison-Wesley, 1969.

N. Kishori, Some aspects of distance concepts in graph theory. Ph. D, Thesis. Karnatak University, Dharwad, pp.81-101, 2007.

H. B. Walikar, S. V. Shinde, I. Baidri and R. H. Roogi, "Square Graphs" an Algorithmic Approach, volume 3, no. 4, International Journal of Advanced Research in Computer Science, 2012.

J. S. Deogun and D. Kratsch, “Diametral Path Graphs,” Graph-Theoretic Concepts in Computer Science, volume 1017, 1995, pp 344-357.

Published

2021-08-28