Title page for etd-0628116-000056


[Back to Results | New Search]

URN etd-0628116-000056
Author Wan-Jyun Chen
Author's Email Address No Public.
Statistics This thesis had been viewed 5563 times. Download 55 times.
Department Applied Mathematics
Year 2015
Semester 2
Degree Master
Type of Document
Language English
Title A study of Steiner number and geodetic number in graphs
Date of Defense 2016-07-18
Page Count 29
Keyword
  • diameter
  • radius
  • Steiner number
  • geodetic number
  • Abstract A u − v geodesic in G is a shortest path between u and v in G. The geodetic interval I_G[u,v] is the set of all vertices which are lying on some u − v geodesic. A geodetic set S of G is a subset of vertices in G such that ∪_ u,v∈S I_G[u,v] = V (G). The geodetic number is the minimum cardinality of a geodetic set in G, denoted by g(G). Let F be a subset of the vertex set of G. A Steiner tree of F in G is a minimum acyclic connected subgraph of G containing F. The Steiner interval of F in G is the collection of vertices lying on some Steiner trees of F in G, denoted by S_G[F]. A Steiner set is the subset F of vertices in G which satisfies S_G[F] = V (G). We call that F is a Steiner set of G. The Steiner number s(G) of G is the minimum cardinality of a Steiner set of G.
    In [9], there is a conjecture: For integers r ≥ 3 and a ≥ b ≥ 3, there exists a connected graph G with rad(G) = diam(G) = r, s(G) = b, and g(G) = a. We study the conjecture and consider the constraint diam(G) = rad(G)+1. In this thesis, we prove the following results:
    (1) There exists a graph G of order 4k + 9 with k ≥ 2, diam(G) = rad(G) = 4, g(G) = 3 + k, and s(G) = 3.
    (2) There exists a graph G of order 4k + 25 with k ≥ 1, diam(G) = rad(G) = 5, g(G) = 4 + k, and s(G) = 3.
    (3) There exists a graph G of order 6k + 12 with k ≥ 1, diam(G) = rad(G) + 1 = 6, g(G) = 2 + k, and s(G) = 3.
    (4) There exists a graph G of order 9k + 15 with k ≥ 1, diam(G) = rad(G) + 1 = 7, g(G) = 3 + k, and s(G) = 3.
    (5) There exists a graph G of order 9k + 12 with k ≥ 1, diam(G) = rad(G) + 1 = 6, g(G) = 2 + 2k, and s(G) =3.
    Keywords: geodetic number; Steiner number; diameter; radius
    Advisory Committee
  • D. J. Guan - chair
  • Hong-Gwa Yeh - co-chair
  • Li-Da Tong - advisor
  • Files
  • etd-0628116-000056.pdf
  • Indicate in-campus at 2 year and off-campus access at 2 year.
    Date of Submission 2016-07-28

    [Back to Results | New Search]


    Browse | Search All Available ETDs

    If you have more questions or technical problems, please contact eThesys