Sezer Sorgun^a , Ali Gokhan Ertas¸ ¨ b , ˙Ibrahim Gunaltılı ¨ c

srgnrzs@gmail.com, aligokhanertas@gmail.com, igunalti@ogu.edu.tr

A configuration of the triple (P,L, I) is an incidence relation which has the properties "any two points are incident with at most one line" and "any two lines are incident with at most one point". In projective geometry, bipartite graphs can be used as an incidence model between the points and lines of a configuration. The graphs associated with a space are a good tool for understanding the topological and geometric properties of space in abstract systems. In this paper we focus on the incidence graph of circular space and obtain its properties in terms of some pure graph invariants. We also characterize it in terms of the graphs associated with other spaces in the literature.

Keywords: bipartite graphs, configuration, circular space Mathematics Subject Classification : 05C72; 05C10

DOI: 10.5614/ejgta.2024.12.2.15

1. Introduction

Let G = (V, E) be a simple graph. If vertices vⁱ and v^j are adjacent, we denote this by viv^j ∈ E(G) or vⁱ ∼ v^j . The degree of any vertex vⁱ is the number of vertices which are adjacent to vⁱ and denoted by d^vi . The distance between the vertices u and v ∈ V (G), denoted by d(u, v), is the minimum length of the paths between u and v. The diameter diam(G) of G is the maximum eccentricity between its vertices, and the radius rad(G) is the minimum eccentricity of its vertices. For an ordered set W = {w1, w2, . . . , wk} ⊆ V (G) and a vertex v of G, we refer to the k-vector

\[r(v|W) = (d(v, w_1), d(v, w_2), \dots, d(v, w_k))\]

Received: 12 March 2024, Revised: 29 September 2024, Accepted: 12 October 2024.

^aDepartment of Mathematics, Nevsehir Hacı Bektas¸ Veli University, Nevsehir 50300, Turkey.

^bDepartment of Informatics, Kutahya Dumlupınar University, K ¨ utahya, 43020, Turkey. ¨

^cDepartment of Mathematics, Eskis¸ehir Osmangazi University, Eskis¸ehir, 26140, Turkey.

as the (metric) representation of v with respect to W. The set W is called a resolving set for G if different vertices have different representations. A resolving set containing a minimum number of vertices is called a minimum resolving set or a basis for G. The (metric) dimension dim(G) is the number of vertices in a basis for G. The metric dimension of some extremal graphs such as path, complete, cycle and complete bipartite graph has been determined in some papers ([8, 15, 4, 5, 1]).

Let N^vi be the set of neighbours of a vertex vⁱ in V (G). Throughout the paper, the common neighbour of the vertices v1, v2, . . . , v^k is denoted as CN(v1, . . . , vk) and its cardinality is denoted as |CN(v1, . . . , vk)| = cn(v1, . . . , vk). A bipartite graph is a graph G(U, W) whose vertex set forms two disjoint sets U and W such that no two graph vertices are adjacent within the same set. Throughout this paper, G(U, W) is considered to be a connected bipartite graph. Given a bipartite graph G(U, W), a graph G′ (U, E′ ) is defined as the projection of the bipartite graph G for the vertex set U with respect to the vertex set W, where V (G′ ) = U and uiu^j ∈ E(G′ ) if CN(uⁱ , u^j ) ̸= ∅ for uⁱ , u^j ∈ U [12].

An incidence structure is a (P,L, σ) triple, where P is a set whose elements are called points, L is a distinct set whose elements are called lines, and σ ⊆ P × L is the incidence relation. For a (P,L, σ) triple, the bipartite graph G with vertex set V = P ∪ L and edge set E = {p, l : pσP} is called an incidence graph. It is also known as a Levi graph [14]. In general, the Levi graph G(π) of a plane π is a bipartite incidence graph with x, y forming an edge in the graph if and only if the point x is on the line y. An incidence structure (P, Z, σ), where P and Z are a set of points and a set of circles, is called a Mobius plane if the following axioms hold ¨

• A1. For any three points, there is exactly one circle containing the points
• A2. For any circle c, any point P ∈ c and Q /∈ c there exists exactly one circle z ′ with P, Q ∈ z ′ and z ∪ z ′ = {P}
• A3. Each circle contains at least three points [9].

Motivated by Levi graphs, Hauschild et al. [10] give a configuration of (P,L, σ) triples on the incidence relation that satisfies the properties "any two points are incident with at most one line" and "any two lines are incident with at most one point". In projective geometry, bipartite graphs can be used as incidence models between the points and lines of a configuration. So the Levi graph of the configuration (P,L, σ) is the bipartite graph G with V (G) = P ∪ L and p ∈ P is adjacent to l ∈ L if and only if pσl [10].

The neighborhood graph N (G) of a graph G = (V, E) is a graph with vertex set V ∪ W, where W is the set of all open neighborhood sets of G, and with two vertices u, w ∈ V ∪ W adjacent if u ∈ V and w is in an open neighborhood set containing u [13]. Kulli [13] gives some characterizations of N (G) for the extremal graph G. In [16] the linear graph (also called bipartite graph) is defined with the help of linear spaces, and some results on the incidence graph (also called Levi graph) of linear graphs are given. A linear graph is a bipartite graph whose parts P and L satisfy two conditions: "For all p, q ∈ P such that p ̸= q, cn(p, q) = 1" and δ(G) ≥ 2. There are also many studies in the literature on the metric dimension of the incidence graphs of the projective plane, the affine plane, generalized quadrangles and the Mobius plane (see, [11, 2, 3] ). ¨

In this paper we study a bipartite graph which is an incidence graph of the circular space given in [7, 6]. We present the properties of the circular graph in terms of graph invariants such as diameter, degree, etc., and we characterize the relationships between the circular graph and the

graphs associated with other spaces which are neighborhood graph, Mobius plane and linear graph.

2. Main Results

Definition 2.1. [6] Let P be a set of points, C be a set of certain distinguished subsets of points called circles and o ⊆ P × C. The incidence structure C = (P, C, o) is called a circular space if:

C1. Every circle contains at least three distinct points.

C2. Any three distinct points are contained in exactly one circle.

Using Definition 2.1, the incidence graph of a circular space can be defined the following:

Definition 2.2. Let G(U, W) be any finite bipartite graph. G is called a circular graph if it satisfies the following conditions

• (i) cn(uⁱ , u^j , uk) = 1 for all uⁱ , u^j , u^k ∈ U.
• (ii) d^w ≥ 3, for all w ∈ W.

If |U| = 1 or |W| = 1, then G is called a trivial circular graph. In this case, it is easy to see that G ∼= K1,n−1. (See Figure 1 and Figure 2.)

Figure 1. Sample of trivial circular graph

Figure 2. Sample of non-trivial circular graph

Lemma 2.1. Let G(U, W) be a circular graph. Then the number of common neighbours of any pair of the vertices in W is at most 2. That's

\[cn(w_1, w_2) \le 2\]

for every w1, w² ∈ W.

Proof. Let G = (U, W) be a circular graph. Suppose that \(|N(w_1) \cap N(w_2)| \ge 3\). Then there exist \((u_i, u_j, u_k)\) triples in the partition U such that \(\{u_i, u_j, u_k\} \subseteq CN(w_1, w_2)\), and hence \(cn(u_i, u_j, u_k) \ge 2\). But this is a contradiction because \(cn(u_i, u_j, u_k) = 1\). Therefore, we have \(cn(w_1, w_2) \le 2\). Note that \(cn(w_1, w_2) \ne 0\).

Theorem 2.3. Let \(\mathcal{T}\) be a family of trees. Then \(T \in \mathcal{T}\) is a circular tree iff \(T \cong K_{1,n-1}\).

Proof. Let T be an arbitrary tree of order n in \(\mathcal{T}\). Since T is also a bipartite graph, we consider as the vertex set \(V = U \cup W\) where \(U = \{u_1, \ldots, u_t\}\) and \(W = \{w_1, \ldots, w_s\}\) such that t + s = n. Now think of T as a circular tree. Then we have \(cn(u_i, u_j, u_k) = 1\) and \(d_{w_i} \geq 3\). From Lemma 2.1 we also know that \(cn(w_i, w_j) \leq 2\) for \(w_i, w_j \in W\). Suppose \(cn(w_i, w_j) = 2\). Then we have \(\{u_1, u_2, u_3\} \subseteq N_{w_i}\) and \(\{u_2, u_3, u_4\} \subseteq N_{w_j}\) for \(u_i \in U\) \((1 \leq u_i \leq 4)\). So we get \(\{u_2, u_3\} \subseteq CN(w_i, w_j)\) and thus T contains the cycle \(w_i - u_2 - w_j - u_3 - w_i\), but this is a contradiction because T is tree. So we have \(cn(w_1, w_2) = 1\) for any pair of vertices \(w_1\) and \(w_2\). Since every triple of \(\{u_i, u_j, u_k\}\) has exactly one common neighbour in W, W must be a singleton partition. That's \(U = \{u_1, \ldots, u_{n-1}\}\) and \(W = \{w_1\}\). So \(T \cong K_{1,n-1}\).

Conversely, if \(T \cong K_{1,n-1}\), it is clear that T is a (trivial) circular tree from Definition 2.2.

Lemma 2.2. Let G(U, W) be a non-trivial circular graph. Then for all \(x \in U\) we have \(d_x \ge 3\).

Proof. Let G(U,W) be a non-trivial circular graph. Then there exists at least \(x \in U\) for \(y \in W\) such that \(x \notin N_y\). From Definition 2.2 (i), for \(\{u_i, u_j, u_k\}\) triples in U we get \(\{u_i, u_j, u_k\} \subseteq N_y\) because \(d_y \geq 3\). Since \(x \notin N_y\), we get \(x \neq u_i, (x \neq u_j, x \neq u_k)\). By Definition 2.2 (ii), there are \(w_1, w_2, w_3\) vertices in W such that \(CN(x, u_i, u_j) = \{w_1\}\), \(CN(x, u_i, u_k) = \{w_2\}\) and \(CN(x, u_i, u_k) = \{w_3\}\).

Since y is not in \(N_x\), then \(y \neq w_1\), \((y \neq w_2, y \neq w_3)\). If \(w_1 = w_2\), then \(cn(u_i, u_j, u_k) \geq 2\). But this contradicts the Definition 2.2 (i). So \(w_1 \neq w_2\). Similarly, we have \(w_1 \neq w_3\) and \(w_2 \neq w_3\). So we get \(d_x \geq 3\) since \(\{w_1, w_2, w_3\} \subseteq N_x\).

Theorem 2.4. Let G(U,W) be a non-trivial circular graph. Then the following holds

• (i) \(d(u_1, u_2) = 2\) for any \(u_1, u_2 \in U\) and \(d(w_1, w_2) = 2\) for \(w_1, w_2 \in W\).
• (ii) \(d(u_1, w_1) \in \{1, 3\}\) for any \(u_1 \in U\) and \(w_1 \in W\).

Proof. (i) Since G is a bipartite graph, \(u_1 \not\sim u_2\) for \(u_1, u_2 \in U\). Then we have \(d(u_1, u_2) \neq 1\) and there is \(w \in W\) such that \(CN(u_1, u_2, u_3) = \{w\}\) for every \(u_3 \in U\) since \(cn(u_1, u_2, u_3) = 1\) in Definition 2.2. So the path between \(u_1\) and \(u_2\) must be the path of \(u_1 - w - u_2\), so we get \(d(u_1, u_2) = 2\). Similarly, \(d(w_1, w_2) \neq 1\) for \(w_1, w_2 \in W\), since G is a bipartite graph. Also by Lemma 2.1 we have \(cn(w_1, w_2) \leq 2\). Let \(1 \leq cn(w_1, w_2) \leq 2\). In this case there is at least one vertex \(u_1\) in U such that \(\{u_1\} \subseteq CN(w_1, w_2)\). So we get \(d(w_1, w_2) = 2\).

(ii) If \(u_1 \in N_{w_1}\) for \(u_1 \in U\) and \(w_1 \in W\), \(d(u_1, w_1) = 1\). If \(u_1 \notin N_{w_1}\), then there exist the vertices \(u_2, u_3, u_4\) in U such that \(u_2, u_3, u_4 \in N_{w_1}\). Since \(cn(u_1, u_2, u_3) = 1\), we have \(w_2 \in W\) such that \(cn(u_1, u_2, u_3) = \{w_2\}\). So the path of \(u_1 - w_2 - u_3 - w_1\) is one of the shortest paths between the vertices \(u_1\) and \(w_1\). Therefore \(d(u_1, w_1) = 3\).

Corollary 2.1. Let G(U, W) be a circular graph.

• (i) If G is trivial circular graph, then diam(G) = 2 and rad(G) = 1.
• (ii) If G is non-trivial circular graph, then diam(G) = 3 and rad(G) = 3.

Proposition 2.1. Let Kⁿ be a complete graph of order n ≥ 3. Consider U = V (Kn) and W = {{a, b, c} : a, b, c are vertices of different triangles in Kn}. Then G = (U ∪ W, E) is a circular graph with uw ∈ E for every u ∈ U and w ∈ W such that u is adjacent to w.

Proof. Let Kⁿ be a complete graph with n ≥ 3 vertices. There are n 3 different triangles in Kn. Let U = V (Kn) and W = {{a, b, c} : distinct triangles in Kn}. Then G = (U ∪W, E) is a circular graph with uw ∈ E for u ∈ U, w ∈ W and u ∈ N(w).

Any uⁱ , u^j , u^k vertices in V (Kn) form a unique triangle in W, so there is only one w in W such that CN(uⁱ , u^j , uk) = {w}. This satisfies condition (i) in Definition 2.2. Also, d(w) = 3 for w ∈ W, which satisfies condition (ii) in Definition 2.2.

Figure 3. CG∆K⁴ triangular circular graph

Figure 4. CG^∆K⁵ triangular circular graph

Remark 2.1. The circular graph, which is constructed in Proposition 2.1, can be defined as triangular circular graph and denoted by CG^∆Kn . Also, ^N (K4) ^∼= CG^∆K⁴

Corollary 2.2. Let G(U, W) be a non-trivial circular graph. Then

\[dim(G) = |U| - 1 \tag{1}\]

Proof. Let G(U, W) be a circular graph. Let U = {u1, . . . , un} and W = {w1, . . . , wm}. Since cn(w1, w2) is at most 2, we have n ≤ m ≤ n 3 . Suppose S ⊆ U is a resolving set such that S = {u1, . . . , uk}, where k < n − 1. Then there are at least two vertices u^t , u^l ̸∈ S but in U. In

this case we get that the representations \(r(u_t|S)=(2,2,\ldots,2)\) and \(r(u_t|S)=(2,2,\ldots,2)\) are the same, since d(u,v)=2 for all \(u,v\in U\) by Theorem 2.4 (i). This contradicts the choice of the set S as the resolving set. Now consider \(S=\{u_1,\ldots,u_{n-1}\}\). Again from Theorem 2.4 (ii), any representation \(r(w_1|S),\ldots,r(w_m|S),r(u_n|S)\) are distinct. Therefore, the set S does indeed resolve all vertices in S.

Proposition 2.2. Let G(U,W) be a circular graph. Then we have \(\mathcal{N}(G) \cong G \cup G\)

Proof. Let G(U,W) be a circular graph, where \(U=\{u_1,u_2,\ldots,u_i\}\) and \(W=\{w_1,w_2,\ldots,w_j\}\). Since the neighbourhood graph is bipartite, \(\mathcal{N}(G)\) is a bipartite graph of order 2(i+j) with vertex partitions \(U\cup W=\{u_1,\ldots,u_i,w_1,\ldots,w_j\}\) and \(N_U\cup N_W=\{N_{u_1},\ldots,N_{u_i},N_{w_1},\ldots,N_{w_j}\}\). For any \(x\in U\) and \(y\in N_U\), the vertices x and y are not adjacent in \(\mathcal{N}\) since \(N_U\subseteq W\). Similarly, \(x\not\sim y\) for \(x\in W\) and \(y\in N_W\). Thus, \(\mathcal{N}(G)\) is a disconnected graph whose components are \(G_1(U,N_W)\) with edge set \(E_1\) and \(G_2(W,N_U)\) with edge set \(E_2\), where \(E_1=\{xy:x\in U,\ y\in N_W\}\) and \(E_2=\{xy:x\in W,\ y\in N_U\}\).

Now, let \(\{u_m, u_n, u_t\}\) be any triple for \(u_m, u_n, u_t \in U\). Then we have \(CN(u_m, u_n, u_t) = w_j\) in G. By identifying \(w_j\) with \(N_{w_j}\), we get \(CN(u_m, u_n, u_t) = \{N_{w_j}\}\) in \(G_1\) because \(u_m, u_n, u_t \subseteq N_{w_j}\). Hence, we see that the neighbourhood of any vertex in G and \(G_1\) are the same, so \(G_1 \cong G\). Similarly, it is easy to see that \(G_2 \cong G\). Therefore, we have \(\mathcal{N}(G) \cong G \cup G\).

Theorem 2.5. Let G(U,W) be a non-trivial circular graph. Define G'(U',W') as a linear graph, where \(U' = U - \{u\}\) and W' = W - S, with \(u \in U\) and \(S = \{x : x \notin N_u\}\). In G', there exists an edge \(u'w' \in E(G')\) for all \(u' \in U'\) and \(w' \in W'\).

Proof. Let G(U,W) be a non-trivial circular graph. Consider \(\{u,q,r\}\) be any triple such that \(CN(u,q,r)=\{w\}\) for \(u,q,r\in U\) and \(w\in W\). Then there is only one \(w'\in W'\) such that \(N_{w'}=N_w-\{u\}=\{q,r\}\). So we get \(CN(q,r)=\{w'\}\) in G'. This satisfies the first condition of a linear graph. Since every pair (q,r) has exactly one common neighbour, we get \(d_{u'}\geq 2\) for \(u'\in U'\). On the other hand, if we delete the vertices in W that are not in the neighbourhood of u, we have \(d_{w'}\geq 2\) for \(w'\in N_u\). So we have \(\delta(G')\geq 2\). This also satisfies the second condition in the definition of a linear graph.

Remark 2.2. As we can see from Theorem 2.5, any linear graph can be an induced subgraph of a circular graph. Also the graph in Figure 5. is a linear graph but not a circular graph.

Figure 5. A linear graph

Corollary 2.3. The incidence graph of a Möbius plane is also a circular graph.

Proof. From the definition of Mobius plane, it is easy to see that the axioms A1 and A2 in M ¨ obius ¨ plane coincide with the two axioms of the circular graph.

Remark 2.3. We know that every incidence graph of the Mobius plane is circular graph from ¨ Corollary 2.3. But the reverse is not true. In Figure 3, the triangular circular graph CG^∆K⁴ is not an incidence graph of the Mobius plane because the second axiom in the definition of the M ¨ obius ¨ plane does not hold.

The conflict of interest and data availability statement

We hereby declare that we have no data related to this manuscript and that no conflicts of interest exist.

References

• [1] S. Akhter and R. Farooq, Metric dimension of fullerene graphs, Electron. J. Graph Theory Appl. 7(1) (2019), 91-103.
• [2] D. Bartoli, T. Heger, G. Kiss, and M. Takats, On the metric dimension of affine planes, biaffine planes and generalized quadrangles, Australas. J. Combin. 72 (2018), 226–248.
• [3] A. Bekes, On the metric dimension of incidence graphs of Mobius planes, ¨ Australas. J. Combin. 82(1) (2022), 59–73.
• [4] G. Chartrand, C. Poisson, and P. Zhang, Resolvability and the upper dimension of graphs, Computers and Mathematics with Applications 39 (2000), 19-28.
• [5] D. Fitriani and S.W. Saputro, The local metric dimension of amalgamation graphs, Electron. J. Graph Theory Appl. 12(1) (2024), 125-146.
• [6] I. Gunaltılı, Z. Akca, and S. Olgun, On finite circular spaces, ¨ Applied Sciences 8 (2006), 85-90.
• [7] I. Gunaltılı and A. Kurtulus, On finite near-circular spaces, ¨ Applied Sciences 6 (2004), 21-26.
• [8] F. Harary and R.A. Melter, On the metric dimension of a graph, Ars. Combin. 2 (1976) 191- 195.
• [9] E. Hartmann, Planar Circle Geometries: An introduction to Moebius, Laguerre and Minkowski-planes, Springer-Verlag, (2004).
• [10] J. Hauschild, J. Ortiz, and O. Vega, On the Levi graph of point-line configurations, Involve, a Journal of Mathematics 8(5) (2015), 893-900.
• [11] T. Heger and M. Takats, Resolving Sets and Semi-Resolving Sets in Finite Projective Planes, Electron. J. Combin. 19(4) (2012), P30.

• [12] M.A. Jothi and K. Sankar, On the metric dimension of bipartite graphs, AKCE Int. J. of Graphs and Comb. (2023) 1-4.
• [13] V.R. Kulli, The neighborhood graph of a graph, International Journal of Fuzzy Mathematical Archive, 8(2) (2015), 93-99.
• [14] F.W. Levi, Finite geometrical systems: six public lectues delivered in February, 1940, at the University of Calcutta, (1942).
• [15] P.J. Slater, Dominating and reference sets in graphs, J. Math. Phys. Sci. 22 (1988), 445-455.
• [16] R. Sunar and I. Gunaltılı, On The Basic Properties of Linear Graphs-I, ¨ Konuralp Journal of Mathematics, 9(1) (2021), 154-158.