Digraf Eksentrik dari Graf Barbel
Eccentric Digraph of Barbell Graph
Abstract
This study investigates the structure of the eccentric digraph ED(G) of barbell graphs, which are formed by connecting two graphs (either complete or cyclic) via a path. The four types of barbell graphs analyzed include: (1) symmetric complete barbell graphs B\left(K_n,P_m\right), (2) asymmetric complete barbell graphs B\left(K_{n_1},K_{n_2},P_m\right), (3) symmetric cyclic barbell graphs B\left(C_n,P_m\right), and (4) asymmetric cyclic barbell graphs B\left(C_{n_1},C_{n_2},P_m\right). The method utilizes the Breadth-First Search (BFS) algorithm to compute vertex eccentricities and determine the direction of arcs in ED(G). The main findings show that for symmetric complete barbell graphs, ED(G) forms a combined structure of K_{n-1,n-1}^\leftrightarrow\ and\ K_{1,n-1}^\rightarrow, with an additional K_{1,2n-2}^\rightarrow component when m is odd. For asymmetric complete barbell graphs, the digraph includes K_{n_1-1,n_2-1}^\leftrightarrow and asymmetrically distributed components K_{1,n_1-1}^\rightarrow\ and\ K_{1,n_2-1}^\rightarrow, depending on the parity of m. In symmetric cyclic barbell graphs, the structure of ED(G) varies according to the parity of n\ and \ m\ , yielding combinations such as \vec{K_{n,1}},\vec{K_{1,1}},\vec{K_{1,2}},or\ \vec{K_{n,2}},\vec{K_{1,4}}. Meanwhile, asymmetric cyclic barbell graphs exhibit additional complexity, where vertex eccentricities are influenced by the interaction among \left\lfloor n_1/2\right\rfloor,\left\lfloor n_2/2\right\rfloor, and the path length m. Overall, the structure of ED(G)is determined by three key factors: the type and symmetry of the component graphs, the parity of the connecting path length, and the diameter relations between components. The BFS algorithm proves effective for analyzing eccentricity in large-scale graphs, and the findings offer a comprehensive theoretical framework for characterizing eccentric digraphs of barbell graph classes.
Collections
- Undergraduate Theses [1470]