Edge hub number in graphs

Shadi Ibrahim Khalaf1, Veena Mathad1, Sultan Senan Mahde1
1Department of Studies in Mathematics, University of Mysore, Manasagangotri, Mysuru – 570 006, INDIA

Abstract

Let \( G \) be a graph, a subset \( S \subseteq E(G) \) is called an edge hub set of \( G \) if every pair of edges \( e, f \in E(G) \setminus S \) are connected by a path where all internal edges are from \( S \). The minimum cardinality of an edge hub set is called the edge hub number of \( G \), and is denoted by \( h_e(G) \). If \( G \) is a disconnected graph, then any edge hub set must contain all of the edges in all but one of the components, as well as an edge hub set in the remaining component. In this paper, the edge hub number for several classes of graphs is computed, and bounds in terms of other graph parameters are also determined.