Geodetic spectra of graphs

被引：7

作者：

Chang, GJ ^{[1
]}

Tong, LD

Wang, HT

机构：

[1] Natl Taiwan Univ, Dept Math, Taipei 106, Taiwan

[2] Natl Sun Yat Sen Univ, Dept Appl Math, Kaohsiung 804, Taiwan

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 2004年 / 25卷 / 03期

关键词：

convex set; geodesic; geodetic number; geodetic spectrum; connected graph; complete graph; cycle; tree; complete r-partite graph;

D O I：

10.1016/j.ejc.2003.09.010

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Geodetic numbers of graphs and digraphs have been investigated in the literature recently. The main purpose of this paper is to study the geodetic spectrum of a graph. For any two vertices u and v in an oriented graph D, a u-v geodesic is a shortest directed path from u to v. Let I (u, v) denote the set of all vertices lying on a u-v geodesic. For a vertex subset A, let I (A) denote the union of all I (u, v) for u, V is an element of A. The geodetic number g (D) of an oriented graph D is the minimum cardinality of a set A with I (A) = V(D). The (strong) geodetic spectrum of a graph G is the set of geodetic numbers of all (strongly connected) orientations of G. In this paper, we determine geodetic spectra and strong geodetic spectra of several classes of graphs. A conjecture and two problems given by Chartrand and Zhang are dealt with. (C) 2003 Published by Elsevier Ltd.

引用

页码：383 / 391

页数：9