An upper bound on the radius of a 3-edge-connected $$C_{4}$$ C 4 -free graph
- PDF / 459,741 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 62 Downloads / 162 Views
An upper bound on the radius of a 3-edge-connected C4 -free graph Blessings T. Fundikwa1 · Jaya P. Mazorodze1 · Simon Mukwembi2 Received: 20 June 2018 / Accepted: 18 September 2020 © African Mathematical Union and Springer-Verlag GmbH Deutschland, ein Teil von Springer Nature 2020
Abstract We give an upper bound on the radius of a C4 -free graph in terms order and edge-connectivity. In particular we show that if G is a 3-edge-connected C4 -free graph of order n and radius r , then the inequality n 58 + 4 4 holds. Moreover, graphs are constructed to show that the bounds are asymptotically sharp. r≤
Keywords Radius · Edge-connectivity Mathematics Subject Classification 05C12
1 Introduction Let G = (V , E) be a finite, connected, undirected graph with vertex set V and edge set E. The distance dG (u, v) between two vertices u, v of G is the length of a shortest u-v path in G. The eccentricity ec(v) of a vertex v ∈ V is the maximum distance between v and any other vertex in G. Every vertex of G of minimum eccentricity is a center vertex of G and the eccentricity of a center vertex is called the radius of G, denoted by rad(G). The degree deg(v) of a vertex v of G is the number of edges incident with v. The minimum degree δ(G) is the minimum of the degrees of vertices in G. The open neighborhood N (v) of a vertex
The results in this paper are part of the Blessings T. Fundikwa MPhilSc thesis.
B
Jaya P. Mazorodze [email protected] Blessings T. Fundikwa [email protected] Simon Mukwembi [email protected]
1
Department of Mathematics, University of Zimbabwe, Harare, Zimbabwe
2
School of Mathematics, Statistics and Computer Science, University of KwaZulu-Natal, Durban, South Africa
123
B. T. Fundikwa et al.
v is the set of all vertices of G adjacent to v. The closed neighborhood N [v] of v is the set N (v) ∪ {v}. The edge-connectivity, λ(G), of G is defined as the minimum number of edges whose deletion from G results in a disconnected or trivial graph. G is k-edge-connected if λ(G) ≥ k. For notions not defined here we refer the reader to [1]. In this paper we are concerned with upper bounds on radius in terms of order and each of the three classical connectivity measures, namely, minimum degree, edge-connectivity and vertex-connectivity for general graphs and for graphs with forbidden subgraphs such as C3 and C4 . Several upper bounds on radius in terms of other graph parameters are known. For example Erd˝os et al. [7] proved that if G is a connected graph of order n and minimum degree δ ≥ 2, then 3(n − 3) rad(G) ≤ +5 (1) 2(δ + 1) and also constructed graphs that, apart from the additive constant, attain the bound. Using different methods, Dankelmann, Dlamini and Swart obtained the slightly stronger result rad(G) ≤
3n + 1. 2(δ + 1)
Bounds on the radius in terms of order and vertex-connectivity were given by Harant and Walther [10]. If κ(G) is even, then the well known bound, diam(G) ≤ (n + κ(G) − 2)/κ(G), on the diameter is also sharp for the radius. For odd κ(G), Harant and Walther [10] showed tha
Data Loading...
