Geodetic Numbers of Graphs
Date Issued
2005
Date
2005
Author(s)
Kang, Chaur-Shang
DOI
en-US
Abstract
All graphs in this thesis are simple, i.e., finite, undirected, loopless and without multiple edges.
For any two vertices u and v of a graph G, a u-v geodesic is a path of length d(u, v). The set I(u, v) consists of all vertices lying on some u-v geodesic of G.. If S is a subset of V(G), then I(S) is the union of all sets I(u, v) for u and v in S. The geodetic number g(G) is the minimum cardinality among the subset S of V(G) with I(S)=V(G).
In section 1, we introduce some definitions, which is used in this thesis.
In section 2, we discuss geodetic numbers on Cartesian products of graphs. The main result is g(G) ≦ g(G□H) for any two graphs G and H. And g(G)=g(G□H) for some H with some special condition.
In section 3, we discuss an upper bound of geodetic numbers of cographs. A 2-N-dominating set of a graph G is a vertex subset D such that every vertex not in D is adjacent to two distinct non-adjacent vertices in D. Denote by g2(G) the minimum cardinality of a 2-N-dominating set in G. And we discuss the relation between geodetic numbers and 2-N-domination numbers.
In section 4, we define tree-cographs and term f-domination. And we design an algorithm to find the 2-N-domination number of a tree-cograph.
Subjects
測地線數
Geodetic Numbers
Type
thesis