On the geodetic number of permutation graphs |
| |
Authors: | Eunjeong Yi |
| |
Institution: | 1. Texas A&M University at Galveston, Galveston, TX, 77553, USA
|
| |
Abstract: | A vertex set S in a graph G is a geodetic set if every vertex of G lies on some u?v geodesic of G, where u,v∈S. The geodetic number g(G) of G is the minimum cardinality over all geodetic sets of G. Let G 1 and G 2 be disjoint copies of a graph G, and let σ:V(G 1)→V(G 2) be a bijection. Then, a permutation graph G σ =(V,E) has the vertex set V=V(G 1)∪V(G 2) and the edge set E=E(G 1)∪E(G 2)∪{uv∣v=σ(u)}. For any connected graph G of order n≥3, we prove the sharp bounds 2≤g(G σ )≤2n?(1+△(G)), where △(G) denotes the maximum degree of G. We give examples showing that neither is there a function h 1 such that g(G)<h 1(g(G σ )) for all pairs (G,σ), nor is there a function h 2 such that h 2(g(G))>g(G σ ) for all pairs (G,σ). Further, we characterize permutation graphs G σ satisfying g(G σ )=2|V(G)|?(1+△(G)) when G is a cycle, a tree, or a complete k-partite graph. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|