Next Article in Journal
DG-GMsFEM for Problems in Perforated Domains with Non-Homogeneous Boundary Conditions
Previous Article in Journal
Density Functional Theory of Highly Excited States of Coulomb Systems
Technical Note

Note on F-Graph Construction

Institute of Applied Informatics, Automation and Mechatronics, Slovak University of Technology in Bratislava, Bottova 25, 917 24 Trnava, Slovakia
*
Author to whom correspondence should be addressed.
Academic Editor: Yudong Zhang
Received: 24 May 2021 / Revised: 21 June 2021 / Accepted: 23 June 2021 / Published: 24 June 2021

Abstract

The center of an F-graph contains at least two vertices, and the distance between any two central vertices is equal to the radius. In this short note, we describe one way of constructing these graphs.
Keywords: eccentricity; center of a graph; F-graph eccentricity; center of a graph; F-graph

1. Introduction

One class of frequently studied central problems in the application of graphs is facility location problems. A cluster of emergency facilities, such as a hospital, a fire station or, a police station, has to locate to a new habitation. We aim to minimize the response time between the facility and the location of a possible emergency. Thus, these facilities are separated as much as possible to minimize the interference [1,2,3]. The simple model of location facilities with those two conditions is an F-graph. The central vertices of F-graphs are as separated as much as possible to minimize the interference between corresponding facilities.
Our terminology and notation are based on [4,5] excluding those given here. Here, we consider nonempty, finite, connected, and undirected graphs without loops and multiple edges. Let d G ( u , v ) denote the distance between the vertices u and v of a graph G = ( V , E ) . The eccentricity is the maximum distance between v and any other vertex u of G; that is, e G ( v ) = max { d G ( u , v ) | u V } . The minimum eccentricity among the vertices of G is the radius r ( G ) , and the set of vertices of G with eccentricity e G ( v ) = r ( G ) is the center. The distance between a vertex v V ( G ) and a nonempty subset S of V ( G ) is the minimum of the distance d G ( v , u ) for every u S .
Buckley and Lewinter define a graph G as an F-graph (the ‘F’ denotes ‘far’) if its center | C ( G ) | 2 and for all u , v C ( G ) is d G ( u , v ) = r ( G ) ; see, e.g., [6]. They also show the existence of such graphs with a prescribed radius and diameter. Kyš gives a necessary and sufficient condition for a graph to be an F-graph [7]. Figure 1 shows an example of an F-graph G, whose radius is r ( G ) = 4 , and the center is the set C ( G ) = { u , v } .

2. Construction of F-Graph

The purpose of this note is to propose a construction for connecting two F-graphs, G 1 and G 2 such that the resulting graph G will also be an F-graph. Let G be a graph with r ( G ) 2 and a center C ( G ) and k be a natural number 1 k r ( G ) . We denote by N G ( k , C ) the set of all vertices v, where d G ( v , C ( G ) ) = k .
Lemma 1.
Let G be an F-graph with r = r ( G ) 2 and k be a natural number 1 k r 2 . Then, the F-graph G contains a nonempty set N G ( k , C ) as a subset of V ( G ) .
Proof. 
Following from the definition of an F-graph, d G ( u , v ) = r for every u , v C ( G ) , u v , and the center contains at least two vertices. Thus, there is at least one shortest path of length r between two different central vertices. There is at least one vertex on this path such that the distance between this vertex and at least one of these two central vertices is k. Thus, N G ( k , C ) is nonempty. □
Lemma 2.
Let G be an F-graph with an even radius r = r ( G ) 2 . Then, for every vertex v where d G ( v , C ( G ) ) r 2 there exists a vertex u in N G ( r 2 , C ) such that d G ( v , u ) r 2 .
Proof. 
Suppose d G ( v , C ( G ) ) < r 2 . Assume to the contrary that there exists v V ( G ) C ( G ) , where d G ( v , C ( G ) ) r 2 such that for every u N G ( r 2 , C ) , there is d G ( v , u ) > r 2 . Suppose that v lies on the shortest path P between two central vertices. Clearly, there is a vertex x from N G ( r 2 , C ) in the middle of P. Thus, d G ( x , v ) r 2 leads to a contradiction. On the other hand, suppose that v does not lie on the shortest path between central vertices. There is just one such vertex c i C ( G ) where d G ( c i , v ) < r 2 . For every c j C ( G ) , i j is d G ( c i , c j ) = r and d G ( c j , v ) > r 2 . Every shortest path from c j to v contains a vertex y from the N G ( r 2 , C ) ; thus, d G ( v , y ) r 2 leads to a contradiction.
Suppose v = c i is a central vertex; thus, d G ( c i , C ( G ) ) = 0 . On shortest path P between c i and other central vertex lies vertex y from the N G ( r 2 , C ) and d G ( c i , y ) = r 2 . Therefore, the proof holds for this case.
Now, suppose d G ( v , C ( G ) ) > r 2 . There is a vertex c C ( G ) such that d G ( v , c ) = d G ( v , C ( G ) ) . The shortest path from v to c contains a vertex z N G ( r 2 , C ) such that d G ( c , z ) = r 2 (Lemma 1); thus, d G ( v , N G ( r 2 , C ) ) r 2 . □
Lemma 3.
Let G be an F-graph with an odd radius r = r ( G ) 2 . Then, for every vertex v such that d G ( v , C ( G ) ) r 2 and d G ( v , C ( G ) ) r 2 , there exists a vertex u in N G ( r 2 , C ) N G ( r 2 , C ) such that d G ( v , u ) r 2 .
Proof. 
Suppose d G ( v , C ( G ) ) < r 2 . Assume to the contrary that there exists v V ( G ) C ( G ) where d G ( v , C ( G ) ) r 2 and d G ( v , C ( G ) ) r 2 such that for every vertex, u N G ( r 2 , C ) N G ( r 2 , C ) is d G ( v , u ) > r 2 . Suppose that v lies on a shortest path P between two central vertices c i , c j . Clearly, there are vertices x , y from N G ( r 2 , C ) N G ( r 2 , C ) such that d G ( c i , x ) = d G ( c j , y ) = r 2 . Thus, d G ( v , x ) r 2 or d G ( v , y ) r 2 leads to a contradiction. On the other hand, suppose that v does not lie on the shortest path between the central vertices. There is just one such vertex c i C ( G ) that d G ( c i , v ) < r 2 . For every c j C ( G ) , i j is d G ( c i , c j ) = r and d G ( c j , v ) > r 2 . Every shortest path from c j to v contains a vertex y from N G ( r 2 , C ) N G ( r 2 , C ) ; thus, d G ( v , y ) r 2 leads to a contradiction.
Suppose v = c i is a central vertex; thus, d G ( c i , C ( G ) ) = 0 . On the shortest path P between other central vertices lies vertex y from N G ( r 2 , C ) N G ( r 2 , C ) such that d G ( c i , y ) = r 2 . Thus, the proof holds for this case.
Suppose d G ( v , C ( G ) ) > r 2 . There is a vertex c C ( G ) such that d G ( v , c ) = d G ( v , C ( G ) ) . The shortest path from v to c contains a vertex z N G ( r 2 , C ) N G ( r 2 , C ) , where d G ( c , z ) = r 2 or d G ( c , z ) = r 2 (Lemma 1); thus, d G ( v , N G ( r 2 , C ) N G ( r 2 , C ) r 2 . □
Theorem 1.
Let G 1 and G 2 be two F-graphs with centers C ( G 1 ) and C ( G 2 ) , respectively, and r ( G 1 ) = r ( G 2 ) = r . Then, there exists an F-graph G with r ( G ) = r and C ( G ) = C ( G 1 ) C ( G 2 ) , containing G 1 and G 2 as induced subgraphs.
Proof. 
We constructed the graph for even radius as illustrated in Figure 2. The construction is based directly on the definition of the F-graph, and, as such, the center contains at least two vertices, and the distance between any two central vertices is equal to the radius. First, it is necessary to ensure that the distance between the central vertices of both graphs is r ( G ) = r ( G 1 ) = r ( G 2 ) . Following from Lemma 1, the F-graph G 1 contains nonempty sets N G 1 ( r 2 1 , C ) and N G 1 ( r 2 , C ) , and G 2 contains nonempty sets N G 2 ( r 2 1 , C ) and N G 2 ( r 2 , C ) . We constructed a complete bipartite graph such that the set N G 1 ( r 2 1 , C ) is the first partition and N G 2 ( r 2 , C ) is the second partition, as well as a complete bipartite graph with sets N G 1 ( r 2 , C ) and N G 2 ( r 2 1 , C ) as partitions. Then, for the set of vertices C ( G ) = C ( G 1 ) C ( G 2 ) , it holds that d G ( x i , x j ) = r for every x i , x j C ( G ) , i j . It is then necessary to ensure that for every vertex y C ( G ) , it holds that e ( v ) > r . For every vertex, x j C ( G ) and x i C ( G ) ; thus, it holds that d G ( x i , x j ) r (Lemma 2). We added four nodes, v 1 , v 2 , u 1 , u 2 , to V ( G ) . Each vertex c C ( G ) is connected by a path with a length of r 2 to nodes v 1 and v 2 . Finally, we added two disjoint paths, v 1 u 1 and v 2 u 2 , with a length of r 2 . Following from the construction, graph G is an F-graph.
Suppose the radius is odd, as shown in Figure 3. It is necessary to ensure that the distance between the central vertices of both graphs is r ( G ) = r ( G 1 ) = r ( G 2 ) and, at the same time, that the distance of the vertex from the center C ( G 1 ) ( C ( G 2 ) ) to the non-central vertex of the graph G 2 ( G 1 ) is d G ( C ( G 1 , V ( G 2 ) C ( G 2 ) ) ) r ( d G ( C ( G 2 , V ( G 1 ) C ( G 1 ) ) ) r ). The existence of sets N G 1 ( r 2 , C ) and N G 2 ( r 2 , C ) is a continuation of Lemma 1. We constructed a complete bipartite graph with those sets as partitions. If there existed the set N G 1 ( r 2 , C ) , then we constructed a complete bipartite graph with N G 1 ( r 2 , C ) and N G 2 ( r 2 , C ) as partitions. Similarly, if there existed the set N G 2 ( r 2 , C ) , then we constructed a complete bipartite graph with N G 1 ( r 2 , C ) and N G 2 ( r 2 , C ) as partitions. Thus, for the set of vertices C ( G ) = C ( G 1 ) C ( G 2 ) , it holds that d G ( x i , x j ) = r for every x i , x j C ( G ) , i j . Following this, it is necessary to ensure that for every vertex y C ( G ) , it holds that e ( v ) > r . For every vertex, x j C ( G ) and x i C ( G ) ; thus, it holds that d G ( x i , x j ) r (Lemma 3). We added four nodes, v 1 , v 2 , u 1 , u 2 , to V ( G ) . Each vertex from the C ( G 1 ) is connected by a path with a length of r 2 with to v 1 and by a path with a length of r 2 to vertex v 2 . Each vertex from the C ( G 2 ) is connected by a path with a length of r 2 to vertex v 2 and by a path with a length of r 2 to vertex v 1 . Finally, we added two disjoint paths, v 1 u 1 and v 2 u 2 , with a length of r 2 . Following from the construction, the graph G is an F-graph. □
F-graphs represent an ideal model for the relocation of emergency facilities to housing estates, towns, etc. Such a model is difficult to apply directly in practice. F-graphs can serve as stepping stones to real applications.

Author Contributions

Conceptualization, V.L.; methodology, V.L.; investigation, V.L.; formal analysis, V.L.; writing—original draft preparation, V.L. and R.V.; writing—review and editing, V.L. and R.V. Both authors have read and agreed to the published version of the manuscript.

Funding

The research was supported by the project SANET II of OPVaI-VA/DP/2018/1.1.3-05 (ITMS2014+ code 313011W988).

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

The authors are grateful to the anonymous referees and Editors for their careful reading, valuable comments, and helpful suggestions, which helped significantly in improving the presentation of this work.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Binay, K.B.; Minati, D.; Subhas, C.N.; Sasanka, R. Constant work-space algorithms for facility location problems. Discret. Appl. Math. 2020, 283, 456–472. [Google Scholar]
  2. Buckley, F. Facility location problems. Coll. Math. J. 1987, 18, 24–32. [Google Scholar]
  3. Buckley, F.; Lewinter, M. Graphs with all diametral paths through distant central nodes. Math. Comput. Model. 1993, 17, 35–41. [Google Scholar] [CrossRef]
  4. Buckley, F.; Lewinter, M. Introductory Graph Theory with Aplications; Waveland Press, Inc.: Long Grove, IL, USA, 2013. [Google Scholar]
  5. Buckley, F.; Harary, F. Distance in Graphs; Addison-Wesley: Redwood City, CA, USA, 1990. [Google Scholar]
  6. Nazeer, W.; Kang, S.M.; Nazeer, S.; Munir, M.; Kousar, I.; Sehar, A.; Kwun, Y.C. On center, periphery and average eccentricity for the convex polytopes. Symmetry 2016, 8, 145. [Google Scholar] [CrossRef]
  7. Kyš, P. Graphs with equidistant central nodes. Australas. J. Comb. 1996, 17, 149–156. [Google Scholar]
Figure 1. Example of F-graph G with center C ( G ) = { u , v } .
Figure 1. Example of F-graph G with center C ( G ) = { u , v } .
Computation 09 00074 g001
Figure 2. Construction of the even radius.
Figure 2. Construction of the even radius.
Computation 09 00074 g002
Figure 3. Construction of the odd radius.
Figure 3. Construction of the odd radius.
Computation 09 00074 g003
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Back to TopTop