Vol. 14 No. 3 (2015): Mapana Journal of Sciences
Research Articles

Minimum Breadth of a Graph

  • Agnes M Tabitha,
  • Reddy L Sudershan
Agnes M Tabitha
Research Scholar, Visvesvaraya Technological University, Belgaum, India;
Bio
Reddy L Sudershan
Professor, C M S Business School, Jain University, Bangalore, India;
Bio
DOI: https://doi.org/10.12723/mjs.34.3

Published 2021-08-28

Keywords

  • Diameter,
  • Radius,
  • Peripheral vertices,
  • Central vertices,
  • Diametral Path,
  • Breadth
    • ...More
    Less

Copyright (c) 2015

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

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.

References

  1. F. Buckley and F. Harary, Distance in Graphs, Perseus Books, 1990.
  2. F. Harary, Graph Theory, Addison-Wesley, 1969.
  3. N. Kishori, Some aspects of distance concepts in graph theory. Ph. D, Thesis. Karnatak University, Dharwad, pp.81-101, 2007.
  4. 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.
  5. J. S. Deogun and D. Kratsch, “Diametral Path Graphs,” Graph-Theoretic Concepts in Computer Science, volume 1017, 1995, pp 344-357.