Electronic Journal of Graph Theory and Applications 12 .
, 379Ae386 On the incidence graph of circular spaces Sezer Sorguna .
Ali GoOkhan Ertasb .
INbrahim GuOnaltlc Department of Mathematics.
Nevsehir Hac Bektas Veli University.
Nevsehir 50300.
Turkey.
b Department of Informatics.
KuOtahya Dumlupnar University.
KuOtahya, 43020.
Turkey.
c Department of Mathematics.
Eskisehir Osmangazi University.
Eskisehir, 26140.
Turkey.
srgnrzs@gmail.
com, aligokhanertas@gmail.
com, igunalti@ogu.
Abstract A configuration of the triple (P.
I) is an incidence relation which has the properties Ayany two points are incident with at most one lineAy and Ayany two lines are incident with at most one pointAy.
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.
Introduction Let G = (V.
E) be a simple graph.
If vertices vi and vj are adjacent, we denote this by vi vj OO E(G) or vi O vj .
The degree of any vertex vi is the number of vertices which are adjacent to vi and denoted by dvi .
The distance between the vertices u and v OO V (G), denoted by d.
, .
, 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 = .
1 , w2 , .
, wk } OI V (G) and a vertex v of G, we refer to the k-vector r.
W ) = .
, w1 ), d.
, w2 ), .
, d.
, wk )) Received: 12 March 2024.
Revised: 29 September 2024.
Accepted: 12 October 2024.
On the incidence graph of circular spaces Sezer Sorgun et al.
as the .
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 .
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 (.
, 15, 4, 5, .
Let Nvi be the set of neighbours of a vertex vi in V (G).
Throughout the paper, the common neighbour of the vertices v1 , v2 , .
, vk is denoted as CN .
1 , .
, vk ) and its cardinality is denoted as |CN .
1 , .
, vk )| = cn.
1 , .
, 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 Throughout this paper.
G(U.
W ) is considered to be a connected bipartite graph.
Given a bipartite graph G(U.
W ), a graph GA (U.
E A ) is defined as the projection of the bipartite graph G for the vertex set U with respect to the vertex set W , where V (GA ) = U and ui uj OO E(GA ) if CN .
i , uj ) = OI for ui , uj OO U .
An incidence structure is a (P.
E) triple, where P is a set whose elements are called points.
L is a distinct set whose elements are called lines, and E OI P y L is the incidence relation.
For a (P.
E) triple, the bipartite graph G with vertex set V = P O L and edge set E = .
, l : pEP} is called an incidence graph.
It is also known as a Levi graph .
In general, the Levi graph G(A) of a plane A 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.
E), where P and Z are a set of points and a set of circles, is called a MoObius 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 OO c and Q OO / c there exists exactly one circle z A with P.
Q OO z A A and z O z = {P } A3.
Each circle contains at least three points .
Motivated by Levi graphs.
Hauschild et al.
give a configuration of (P.
E) triples on the incidence relation that satisfies the properties Ayany two points are incident with at most one lineAy and Ayany two lines are incident with at most one pointAy.
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.
E) is the bipartite graph G with V (G) = P O L and p OO P is adjacent to l OO L if and only if pEl .
The neighborhood graph N (G) of a graph G = (V.
E) is a graph with vertex set V O W , where W is the set of all open neighborhood sets of G, and with two vertices u, w OO V O W adjacent if u OO V and w is in an open neighborhood set containing u .
Kulli .
gives some characterizations of N (G) for the extremal graph G.
In .
the linear graph .
lso called bipartite grap.
is defined with the help of linear spaces, and some results on the incidence graph .
lso called Levi grap.
of linear graphs are given.
A linear graph is a bipartite graph whose parts P and L satisfy two conditions: AyFor all p, q OO P such that p = q, cn.
, .
= 1Ay and (G) Ou 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 MoObius plane .
ee, .
, 2, .
In this paper we study a bipartite graph which is an incidence graph of the circular space given in .
, .
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 On the incidence graph of circular spaces Sezer Sorgun et al.
graphs associated with other spaces which are neighborhood graph.
Mobius plane and linear graph.
Main Results Definition 2.
Let P be a set of points.
C be a set of certain distinguished subsets of points called circles and o OI P y C.
The incidence structure C = (P.
C, .
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.
Let G(U.
W ) be any finite bipartite graph.
G is called a circular graph if it satisfies the following conditions .
i , uj , uk ) = 1 for all ui , uj , uk OO U .
dw Ou 3, for all w OO W .
If |U | = 1 or |W | = 1, then G is called a trivial circular graph.
In this case, it is easy to see that GO = K1,nOe1 .
(See Figure 1 and Figure 2.
Figure 1.
Sample of trivial circular graph Figure 2.
Sample of non-trivial circular graph Lemma 2.
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.
ThatAos cn.
1 , w2 ) O 2 for every w1 , w2 OO W .
On the incidence graph of circular spaces Sezer Sorgun et al.
Proof.
Let G = (U.
W ) be a circular graph.
Suppose that |N .
1 ) O N .
2 )| Ou 3.
Then there exist .
i , uj , uk ) triples in the partition U such that .
i , uj , uk } OI CN .
1 , w2 ), and hence cn.
i , uj , uk ) Ou But this is a contradiction because cn.
i , uj , uk ) = 1.
Therefore, we have cn.
1 , w2 ) O 2.
Note that cn.
1 , w2 ) = 0.
Theorem 2.
Let T be a family of trees.
Then T OO T is a circular tree iff T O = K1,nOe1 .
Proof.
Let T be an arbitrary tree of order n in T .
Since T is also a bipartite graph, we consider as the vertex set V = U O W where U = .
1 , .
, ut } and W = .
1 , .
, ws } such that t s = n.
Now think of T as a circular tree.
Then we have cn.
i , uj , uk ) = 1 and dwi Ou 3.
From Lemma 1 we also know that cn.
i , wj ) O 2 for wi , wj OO W .
Suppose cn.
i , wj ) = 2.
Then we have .
1 , u2 , u3 } OI Nwi and .
2 , u3 , u4 } OI Nwj for ui OO U .
O ui O .
So we get .
2 , u3 } OI CN .
i , wj ) and thus T contains the cycle wi Oe u2 Oe wj Oe u3 Oe wi , but this is a contradiction because T is tree.
So we have cn.
1 , w2 ) = 1 for any pair of vertices w1 and w2 .
Since every triple of .
i , uj , uk } has exactly one common neighbour in W .
W must be a singleton partition.
ThatAos U = .
1 , .
, unOe1 } and W = .
1 }.
So T O = K1,nOe1 .
Conversely, if T = K1,nOe1 , it is clear that T is a .
circular tree from Definition 2.
Lemma 2.
Let G(U.
W ) be a non-trivial circular graph.
Then for all x OO U we have dx Ou 3.
Proof.
Let G(U.
W ) be a non-trivial circular graph.
Then there exists at least x OO U for y OO W such that x OO Ny .
From Definition 2.
, for .
i , uj , uk } triples in U we get .
i , uj , uk } OI Ny because dy Ou 3.
Since x OO Ny , we get x = ui , .
= uj , x = uk ).
By Definition 2.
, there are w1 , w2 , w3 vertices in W such that CN .
, ui , uj ) = .
1 }.
CN .
, ui , uk ) = .
2 } and CN .
, uj , uk ) = .
3 }.
Since y is not in Nx , then y = w1 , .
= w2 , y = w3 ).
If w1 = w2 , then cn.
i , uj , uk ) Ou 2.
But this contradicts the Definition 2.
So w1 = w2 .
Similarly, we have w1 = w3 and w2 = w3 .
So we get dx Ou 3 since .
1 , w2 , w3 } OI Nx .
Theorem 2.
Let G(U.
W ) be a non-trivial circular graph.
Then the following holds .
1 , u2 ) = 2 for any u1 , u2 OO U and d.
1 , w2 ) = 2 for w1 , w2 OO W .
1 , w1 ) OO .
, .
for any u1 OO U and w1 OO W .
Proof.
Since G is a bipartite graph, u1 O u2 for u1 , u2 OO U .
Then we have d.
1 , u2 ) = 1 and there is w OO W such that CN .
1 , u2 , u3 ) = .
for every u3 OO U since cn.
1 , u2 , u3 ) = 1 in Definition 2.
So the path between u1 and u2 must be the path of u1 Oe w Oe u2 , so we get d.
1 , u2 ) = 2.
Similarly, d.
1 , w2 ) = 1 for w1 , w2 OO W , since G is a bipartite graph.
Also by Lemma 2.
1 we have cn.
1 , w2 ) O 2.
Let 1 O cn.
1 , w2 ) O 2.
In this case there is at least one vertex u1 in U such that .
1 } OI CN .
1 , w2 ).
So we get d.
1 , w2 ) = 2.
If u1 OO Nw1 ) for u1 OO U and w1 OO W , d.
1 , w1 ) = 1.
If u1 OO / Nw1 , then there exist the vertices u2 , u3 , u4 in U such that u2 , u3 , u4 OO Nw1 .
Since cn.
1 , u2 , u3 ) = 1, we have w2 OO W such that cn.
1 , u2 , u3 ) = .
2 }.
So the path of u1 Oe w2 Oe u3 Oe w1 is one of the shortest paths between the vertices u1 and w1 .
Therefore d.
1 , w1 ) = 3.
On the incidence graph of circular spaces Sezer Sorgun et al.
Corollary 2.
Let G(U.
W ) be a circular graph.
If G is trivial circular graph, then diam(G) = 2 and rad(G) = 1.
If G is non-trivial circular graph, then diam(G) = 3 and rad(G) = 3.
Proposition 2.
Let Kn be a complete graph of order n Ou 3.
Consider U = V (Kn ) and W = {.
, b, .
: a, b, c are vertices of different triangles in Kn }.
Then G = (U O W.
E) is a circular graph with uw OO E for every u OO U and w OO W such that u is adjacent to w.
Proof.
Let Kn be a complete graph with n Ou 3 vertices.
There are n3 different triangles in Kn .
Let U = V (Kn ) and W = {.
, b, .
: distinct triangles in Kn }.
Then G = (U OW.
E) is a circular graph with uw OO E for u OO U , w OO W and u OO N .
Any ui , uj , uk vertices in V (Kn ) form a unique triangle in W , so there is only one w in W such that CN .
i , uj , uk ) = .
This satisfies condition .
in Definition 2.
Also, d.
= 3 for w OO W , which satisfies condition .
in Definition 2.
Figure 3.
CGOIK4 triangular circular graph Figure 4.
CGOIK5 triangular circular graph Remark 2.
The circular graph, which is constructed in Proposition 2.
1, can be defined as triangular circular graph and denoted by CGOIKn .
Also.
N (K4 ) O
= CGOIK4
Corollary 2.
Let G(U.
W ) be a non-trivial circular graph.
Then dim(G) = |U | Oe 1 Proof.
Let G(U.
W ) be a circular graph.
Let U = .
1 , .
, un } and W = .
1 , .
, wm }.
Since cn.
1 , w2 ) is at most 2, we have n O m O n3 .
Suppose S OI U is a resolving set such that S = .
1 , .
, uk }, where k < n Oe 1.
Then there are at least two vertices ut , ul OO S but in U .
On the incidence graph of circular spaces Sezer Sorgun et al.
this case we get that the representations r.
t |S) = .
, 2, .
, .
and r.
l |S) = .
, 2, .
, .
are the same, since d.
, .
= 2 for all u, v OO U by Theorem 2.
This contradicts the choice of the set S as the resolving set.
Now consider S = .
1 , .
, unOe1 }.
Again from Theorem 2.
, any representation r.
1 |S), .
, r.
m |S), r.
n |S) are distinct.
Therefore, the set S does indeed resolve all vertices in G.
Proposition 2.
Let G(U.
W ) be a circular graph.
Then we have N (G) O
=GOG
Proof.
Let G(U.
W ) be a circular graph, where U = .
1 , u2 , .
, ui } and W = .
1 , w2 , .
, wj }.
Since the neighbourhood graph is bipartite.
N (G) is a bipartite graph of order 2.
with vertex partitions U O W = .
1 , .
, ui , w1 , .
, wj } and NU O NW = {Nu1 , .
Nui .
Nw1 , .
Nwj }.
For any x OO U and y OO NU , the vertices x and y are not adjacent in N since NU OI W .
Similarly, x O y for x OO W and y OO NW .
Thus.
N (G) is a disconnected graph whose components are G1 (U.
NW ) with edge set E1 and G2 (W.
NU ) with edge set E2 , where E1 = .
y : x OO U, y OO NW } and E2 = .
y : x OO W, y OO NU }.
Now, let .
m , un , ut } be any triple for um , un , ut OO U .
Then we have CN .
m , un , ut ) = wj in By identifying wj with Nwj , we get CN .
m , un , ut ) = {Nwj } in G1 because um , un , ut OI Nwj .
Hence, we see that the neighbourhood of any vertex in G and G1 are the same, so G1 O = G.
Similarly, it is easy to see that G2 O = G.
Therefore, we have N (G) O = G O G.
Theorem 2.
Let G(U.
W ) be a non-trivial circular graph.
Define GA (U A .
W A ) as a linear graph, where U A = U Oe .
and W A = W Oe S, with u OO U and S = .
: x OO Nu }.
In GA , there exists an edge uA wA OO E(GA ) for all uA OO U A and wA OO W A .
Proof.
Let G(U.
W ) be a non-trivial circular graph.
Consider .
, q, .
be any triple such that CN .
, q, .
= .
for u, q, r OO U and w OO W .
Then there is only one wA OO W A such that NwA = Nw Oe .
= .
, .
So we get CN .
, .
= .
A } in GA .
This satisfies the first condition of a linear graph.
Since every pair .
, .
has exactly one common neighbour, we get duA Ou 2 for uA OO U A .
On the other hand, if we delete the vertices in W that are not in the neighbourhood of u, we have dwA Ou 2 for wA OO Nu .
So we have (GA ) Ou 2.
This also satisfies the second condition in the definition of a linear graph.
Remark 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.
The incidence graph of a MoObius plane is also a circular graph.
On the incidence graph of circular spaces Sezer Sorgun et al.
Proof.
From the definition of MoObius plane, it is easy to see that the axioms A1 and A2 in MoObius plane coincide with the two axioms of the circular graph.
Remark 2.
We know that every incidence graph of the MoObius plane is circular graph from Corollary 2.
But the reverse is not true.
In Figure 3, the triangular circular graph CGOIK4 is not an incidence graph of the MoObius plane because the second axiom in the definition of the MoObius 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