Some Upper Bounds Related with Domination Number
- PDF / 395,624 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 112 Downloads / 194 Views
Some Upper Bounds Related with Domination Number Zhao Gu · Jixiang Meng · Zhao Zhang · Jin E. Wan
Received: 8 November 2012 / Revised: 20 March 2013 / Accepted: 22 March 2013 / Published online: 25 April 2013 © Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg 2013
Abstract For a simple and connected graph G, denote the domination number, the diameter, and the radius of G as β(G), D(G), and r(G), respectively. In this paper, we solve two conjectures on the upper bounds of β(G) · D(G) and β(G) + r(G), which are proposed by the computer system AutoGraphiX. Extremal trees which attain the upper bounds are also considered. Keywords AutoGraphiX · Upper bounds · Extremal tree · Domination number
1 Introduction and Notation A group of people under the name of GERAD developed a computer system called AutoGraphiX (AGX) based on [1, 2]. AGX is used to aid posing conjectures in graph theory and finding extremal graphs related to graph parameters. In this paper, we solve two conjectures proposed by AGX [5]. To introduce the conjectures, we first introduce some terminologies. Let G = (V , E) be a connected simple graph with n vertices. Denote by NG (v) the set of neighbors of vertex v in G. If there is no danger of confusion, subscript G is omitted. A set S ⊆ V (G) is a dominating set of G if for any v ∈ V , either v ∈ S or N(v)∩S = ∅. The domination number β(G) of a graph G is the minimum cardinality of a dominating set of G. Let d(u, v) be the length of a shortest path connecting
This work was supported by National Natural Science Foundation of China (Nos. 61222201, 11171283). Z. Gu () · J. Meng · Z. Zhang College of Mathematics and System Sciences, Xin Jiang University, Urumqi 830046, China e-mail: [email protected] J.E. Wan College of Information Science and Engineering, Xin Jiang University, Urumqi 830046, China
218
Z. Gu et al.
Fig. 1 T (20; 1, 2, 3, 4, 2, 1, 7)
u and v. The eccentricity of vertex v in G is ecc(v) = max{d(v, u) : u ∈ V }. The diameter D(G) = max{ecc(v) : v ∈ V } and the radius r(G) = min{ecc(v) : v ∈ V }. The family of graphs T (l; k1 , k2 , · · · , kt ) is defined by the following algorithm: For a length-(l − 1) path Pl : v1 v2 · · · vl , do nothing to the first k1 vertices, then pend a vertex to every vertex of the following k2 vertices, do nothing to the next k3 vertices, pend a vertex to every vertex of the next k4 vertices, and so on. The vertex of Pl which was pended a vertex is called attachment vertex. Take T (20; 1, 2, 3, 4, 2, 1, 7) for an example (see Fig. 1). The family of graphs T (l; k1 , k2 , · · · , kt ; p1 , G1 ; p2 , G2 ; · · · ; pq , Gq ) is the graph obtained from T (l; k1 , k2 , · · · , kt ) by pending graph Gj to vertex vpj for j = 1, 2, · · · , q. Let Pn be a path on n vertices. The following are two conjectures proposed in [5] (we restate them using the above terminologies). Conjecture 1.1 (Conjecture A.328-U in [5]) For any graph G on n vertices, (n + 3)(n − 2)/3, if n ≡ 0 (mod 3), β(G) · D(G) n/
Data Loading...
