Hub Number of Incidence and Power Graph

Document Type : Research Article

Authors

1 Department of Mathematics, University of Zanjan, Zanjan, Iran

2 Department of Mathematics, Zanjan Branch, Islamic Azad university, Zanjan, Iran

Abstract

In graph theory, a set $H \subseteq V (G)$ is defined as a hub set if every pair of non-adjacent vertices outside $H$ can be interconnected by a path that exclusively traverses through the internal vertices contained in $H$. The hub number of a graph $G$ refers to the minimal cardinality of such a hub set, providing crucial insights into the structural connectivity of the graph. This paper delves into the exploration of the hub number across various graph structures, specifically focusing on incidence graphs and square graphs, both of which possess unique characteristics impacting their connectivity properties. We establish theoretical bounds for the hub numbers of these graphs, facilitating a clearer understanding of their structural complexities. Furthermore, we derive explicit values for the hub numbers of several special types of graphs, including path graphs, star graphs and complete graphs. Through rigorous analysis and evaluation, this study contributes to the broader field of connectivity in graphs by not only identifying the hub numbers for specific examples but also by proposing methodologies for their computation. These findings have important implications for applications in network design and graph optimization, enhancing the utility of hub sets in practical scenarios.

Keywords

Main Subjects

Full Text

 

Article PDF

References

[1] H. Fleischner, The square of Every Two-Connected Graph is hamiltonian, Department of Mathematics, J. comb. Theory (B),16, 323–339, (1974).
[2] T. Grauman, S. G. Hartke, A. Jobson, B. Kinnersley, D. B. West, L. Wiglesworth, P. Worah and H. Wu, The hub number of a graph, Inform. Process. Lett. 108, 226–228, (2008).
[3] P. Johnson, P. Slater, M. Walsh, The connected hub number and the connected domination number, Networks, Wiley Online Library, 58, 232–237, (2011).
[4] M. Walsh, The hub number of a graph, Intl. J. Math. Comput. Sci. 1, 117–124, (2006).
[5] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, 2001.
[6] Z. Zhong-fu, Y. Bing, L. Jing-wen, L. Lin-zhong, W. Jian-fang and X. Bao-gen, On Incidence Graphs, Ars Comb. 87, 213–223, (2008).
Analytical and Numerical Solutions for Nonlinear Equations
Volume 9, Issue 1
May 2024
Pages 60-64

Files

History

  • Receive Date: 12 March 2025
  • Revise Date: 17 May 2025
  • Accept Date: 24 May 2025
  • Publish Date: 31 May 2025

Share

How to cite

Statistics