# Affine Graphs and their Topological Indices

Authors: Abdurrahman Dayioglu
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Graphs are essential tools to illustrate relationships in given datasets visually. Therefore, generating graphs from another concept is very useful to understand it comprehensively. This paper will introduce a new yet simple method to obtain a graph from any finite affine plane. Some combinatorial properties of the graphs obtained from finite affine planes using this graph-generating algorithm will be examined. The relations between these combinatorial properties and the order of the affine plane will be investigated. Wiener and Zagreb indices, spectrums, and energies related to affine graphs are determined, and appropriate theorems will be given. Finally, a characterization theorem will be presented related to the degree sequences for the graphs obtained from affine planes.


---

## Body

## 1. Introduction

In this section, we start with some definitions and fundamental notions regarding affine planes from [1].Definition 1.
An affine planeA is an ordered pair P,ℒ which we call the elements of P as points and the elements of ℒ as lines, with the following properties:(A1)
Any two distinct points lie on a unique line(A2)
For each pointp not on a line l, there is exactly one line l′ passing through p such that l is parallel to l′(A3)
There exists a set of three noncollinear points.
The linesl and l′ are called as parallel if l∩l′=ϕ or l=l′, and we denote this by(1)ll′.
Condition (A2) is also called asparallel axiom.
IfP∪ℒ is a finite set, then the affine plane A=P,ℒ is called as finite affine plane.
Let us supposeA is an affine plane. We know from [1] that, in the affine planes, the number of points on each line is the same. Letting k be the number of points per line in A, we call k the order of A. Accordingly any point is on k+1 lines.
IfA has order k, then(1)
A has k2 points(2)
Each line is parallel tok lines(3)
A has k2+k lines(4)
Each linel meets k2 other lines(5)
There arek+1 parallel classesExample 1.
In [1], it is shown that the smallest affine plane has four points and six lines and is described synthetically as(2)P=1,2,3,4,ℒ=l1=1,2,l2=3,4,l3=1,3,l4=2,4,l5=1,4,l6=2,3.
The lines can be grouped into three sets of parallel lines:(3)l1l2,l3l4,l5l6.
P,ℒ is the affine plane presented in Figure 1.
When a finite affine plane is given, there is a numberk≥2 as the order. However, for a given number k, it is not necessary to have an affine plane of order k. It is a matter of ongoing studies that whether or not there are affine planes in which order.
Let us now recall some fundamental notions of graph theory from [2–6] to make the paper more self-contained.
LetG=V,E be a multigraph with order n and size m, defined as the number of vertices and the number of edges, respectively. Let u and v be two vertices in graph G. If e=u,v is an edge, then it can be written as e=uv, and the vertices u and v are called as adjacent verticesu∼v and so the ends of e. The edge e=u,v is said to be incident with u and v. An edge with identical ends is called a loop, and an edge with distinct ends a link. Two or more links with the same pair of ends are said to be parallel edges.
A graphG is called simple if it has neither loops nor parallel edges. During this work, we are going to deal with simple graphs.
A graphG is said to be regular if every vertex in G has the same degree. More precisely, G is said to be k-regular if dv=k for each vertex v in G, where k≥0. Adjacency matrixA of G defined as follows: A=AG=aij, where(4)aij=1,ifi∼j,aij=0,otherwise.
Obviously,A is a symmetric matrix with zero diagonal; entries consist of 0’s and 1’s. The eigenvalues of A are the n roots of the characteristic polynomialdetxI−A, so they are algebraic integers. The characteristic polynomial of G is denoted by PGx.Figure 1
Affine plane of order 2.Definition 2.
The spectrum of a finite graphG is the spectrum of the adjacency matrix A, that is, its set of eigenvalues together with their multiplicities.
The eigenvalues represented asλ1,λ2,…,λn, and unless we indicate otherwise, we shall assume that λ1≥λ2≥⋯≥λn. If G has distinct eigenvalues μ1,μ2,…,μm with multiplicities k1,k2,…,km, respectively, we shall write μ1k1,μ2k2,…,μmkm for the spectrum of G.
LetG be a graph with n vertices and m edges m>0. The energyEGofG is defined by(5)EG=∑i=1nλi,where λ1,λ2,…,λn are the eigenvalues of G.
A topological index related to a graph is a real number that must be a structural invariant. The topological indices are important for numerical relationships with the structure.Definition 3.
LetG be a graph with vertex set VG and edge set EG. The distance dGu,v between two vertices u,v∈VG is the minimum number of edges on a path in G between u and v. The Wiener index WG of G is defined by(6)WG=∑u,v⊆VGdGu,v.
The distancedGu of a vertex u is the sum of all distances between u and all other vertices of G. Thus, we can define the Wiener index as below:(7)WG=12∑u∈VGdGu.
Two of the most useful topological graph indices are thefirst and second Zagreb indices which have been introduced by Gutman and Trinajstic in [7]. They are denoted by M1G and M2G and were defined as(8)M1G=∑u∈VGdu2,M2G=∑uv∈EGdudv,respectively.


## 2. The Relation of Graphs with Finite Affine Planes

Affine planes are one of the fundamental examples of incidence geometry. Considering the interpretation of graphs to social sciences and their application to network technologies, with the regularity and parallelism classes of affine planes, it is an interesting issue to obtain graphs from affine planes as one of the transitionalities that can yield results that are most logical and suitable for real-life practices.We are going to be in an investigation for the answer to the following question: what if someone perceives the lines of a geometric structure as an element of graph theory and what could be obtained from this? To do so, we are introducing a new perspective. In this study, we work only with finite affine planes.


### 2.1. The Method of Obtaining Graphs from Finite Affine Planes

In this part, a method will be presented to obtain a graph from a given finite affine plane. We note that obtaining a graphG=V,E from a finite affine plane A=P,ℒ, which itself is already a graph G=A, is pointless, but still the method we are going to introduce remains valid for such affine planes.Definition 4.
(1) LetA=P,ℒ be a finite affine plane of order k. If li is a line, then it must have k points. We take this line as an ordered k-tuple li=li1,li2,li3,…,lik. It is obvious that k≥2. We establish a new set “sli” for any line li=li1,li2,li3,…,lik in A such that if k=2, then li=li1,li2, and we define(9)sli≔li,and if k≥3, then first we define(10)li,j≔lij,lij+1,1≤j<k,lik,li1,j=k,and second(11)sli≔li,j|j=1,2,…,k≔li,1,li,2,li,3,…,li,k−1,li,k≔li1,li2,li2,li3,…,lik−1,lik,lik,li1.
Throughout this papersli is called as ordered k-gon corresponding to line li when k≥3.
If we try to obtain a graph from a finite affine planeA=P,ℒ, then we have to change our perception of lines. To do so, we use the method introduced in Definition 4.
Let us consider a lineli=li1,li2,li3,…,lik. If k≥3, for 1≤r≤k, any point lir is incident with only li,r−1 and li,r.
For a lineli=li1,li2,li3,…,lik, if k≥3, sli can be considered as a Ck. Also, we know that a C3 is often called a triangle, a C4 is a quadrilateral, a C5 is a pentagon, a C6 is a hexagon, and so on.
In the following theorem, we obtain a graph from a finite affine planeA of any order by considering every element of obtained sli for a line li, as an edge. It is obvious that every element of sli obtained from li is a set of exactly two points.Theorem 1.
IfA=P,ℒ is a finite affine plane of order k, then we have a graph G=V,E such that(12)VG=P,EG=∪li∈ℒsli.Proof.
For any lineli=li1,li2,li3,…,lik∈ℒ, it is trivial that li=k≥2 and every set li,j consists of exactly 2 vertices.
Letx,y∈VG=P be distinct elements. From (A1), there exists only one line(13)li=li1,li2,…,lik,passing through the points x and y. Therefore, for 1≤r,t≤k, there exists(14)x=lir,y=lit,in li. Since r≠t, we take r<t without loss of generality.
Whent = r + 1, there is an edge,(15)li,r=lir,lir+1=lir,lit=x,y,incident with x and y. In other words, when t=r+1, there is only one edge passing through x and y and that is li,r.
Whent>r+1 if t=k and r=1, then there is an edge,(16)li,k=lik,li1=lit,lir=y,x,incident with y and x. In other words, when t>r+1 if t=k and r=1, there is only one edge passing through y and x and that is li,k.
In other cases, it is obvious from the construction ofsli that there is no edge incident with x and y. Thus, we show that G=V,E is a graph.
Throughout this work, we are going to use the method introduced by Theorem1 to obtain a graph from a finite affine plane unless otherwise noted.
We should point out that we have already developed a new and different algorithm to create a new graph generating system from various incidence structures.Corollary 1.
IfA=P,ℒ is a finite affine plane of order k and the graph G=V,E is obtained from A, then EG=ℒ if and only if A is the smallest affine plane.Proof.
We know that if graphG=V,E is obtained from A, then(17)VG=P,EG=∪li∈ℒsli.
Firstly, let us assumeEG=ℒ. For every line li=li1,li2,…,lik of A, if k≠2, then we have an ordered k-gon corresponding to that li which causes a differentiation (an increase on the number of edges) between the number of edges of EG and the number of lines of ℒ. For that reason, k must be 2 for every line li=li1,li2,…,lik of A. It means that A is the affine plane of order 2 which is the smallest one.
Secondly, let us assumeA is the smallest affine plane. For every line li=li1,li2,…,lik of A, we know that k=2. From Definition 4, we always get the k=2 condition which implies for every line, and we get the result(18)sli=li.
SinceEG=∪li∈ℒsli, we obtain(19)EG=li|li∈ℒ=ℒ.Corollary 2.
For a graphG=V,E which is obtained from an affine plane A=P,ℒ,(20)EG=ℒ⇔G=A.Proof.
From Theorem1, we know that(21)VG=P,EG=∪li∈ℒsli.
IfEG=ℒ, then G=A since VG,EG=P,ℒ.
We found that(22)G=A⇒V,E=P,ℒ,⇒VG=P∧EG=ℒ,⇒EG=ℒ,since the equality of ordered pairs dictates one by one equality.
If there were no conditionVG=P in Theorem 1, then the equality of EG and ℒ would not imply the equality of G and A.Definition 5.
A graph obtained from an affine planeA of order k is called as “affine graph of order k corresponding to A,” or if there will not be any confusion, “affine graph of order k ” can be used.
Now, we will examine how affine graphs are obtained when the affine plane of order 2 and the affine plane of order 3 is taken asA=P,ℒ.Example 2.
We are going to investigate the graph obtained from the smallest affine plane given in Example1.
In this situation, as a result of Corollary1 and Corollary 2, we do not need to make any further arrangement for the set of the points and lines because the smallest affine plane is also a graph itself:(23)VG=1,2,3,4=P,EG=l1=1,2,l2=3,4,l3=1,3,l4=2,4,l5=1,4,l6=2,3=ℒ,where G=V,E is a graph and has 4 vertex and 6 edges. If we determine the vertex degrees for each vertex, we obtain(24)d1=d2=d3=d4=3,3,3,3,3=34.
Thus,G is a 3-regular graph (cubic graph) with the degree sequence as above.
Adjacency matrix forG is given below:(25)AG=0111101111011110,where G has spectrum 3,−13 and the energy of G is EG=6.
The Wiener index ofG is(26)WG=12∑u∈VGdGu=12⋅3+3+3+3=6.
Zagreb indices ofG is(27)M1G=∑u∈VGdu2=32+32+32+32=4⋅32=36,M2G=∑uv∈EGdudv=3⋅3+3⋅3+3⋅3+3⋅3+3⋅3+3⋅3=6⋅32=54.Example 3.
Let us take the affine plane of order 3 with points and lines given, respectively,(28)P′=1,2,3,4,5,6,7,8,9,ℒ′=l1=1,2,3,l2=4,5,6,l3=7,8,9,l4=1,4,7,l5=2,5,8,l6=3,6,9,l7=1,5,9,l8=2,6,7,l9=3,4,8,l10=3,5,7,l11=1,6,8,l12=2,4,9,and illustrated by Figure 2.
With the method given earlier, we know thatVG=P. Every given line li=li1,li2,…,lik in this affine plane of order 3 consists of 3 elements. So, k is 3 in every step of obtaining sli. In other words, every line of this affine plane considered as an ordered 3-gon which is denoted as C3 in graph theory. See Figure 3.
The vertex and edge sets of the graphG′ that is obtained from the affine plane of order 3 are as follows:(29)VG′=1,2,3,4,5,6,7,8,9,EG′=l1,1=1,2,l1,2=2,3,l1,3=3,1,l2,1=4,5,l2,2=5,6,l2,3=6,4,l3,1=7,8,l3,2=8,9,l3,3=9,7,l4,1=1,4,l4,2=4,7,l4,3=7,1,l5,1=2,5,l5,2=5,8,l5,3=8,2,l6,1=3,6,l6,2=6,9,l6,3=9,3,l7,1=1,5,l7,2=5,9,l7,3=9,1,l8,1=2,6,l8,2=6,7,l8,3=7,2,l9,1=3,4,l9,2=4,8,l9,3=8,3,l10,1=3,5,l10,2=5,7,l10,3=7,3,l11,1=1,6,l11,2=6,8,l11,3=8,1,l12,1=2,4,l12,2=4,9,l12,3=9,2,where G′ is a graph and has 9 vertex and 36 edges. If we determine the vertex degrees for each vertex, we obtain(30)d1=d2=d3=d4=d5=d6=d7=d8=d9=8,8,8,8,8,8,8,8,8,8=89.
Thus,G′ is a 8-regular graph with the degree sequence as above. Adjacency matrix for G′ is given below:(31)AG′=011111111101111111110111111111011111111101111111110111111111011111111101111111110,where G′ has spectrum 8,−18 and the energy of G′ is EG′=16. See Figure 4.
The Wiener index ofG′ is(32)WG′=12∑u∈VG′dG′u=12⋅8+8+8+⋯+8=36.
Zagreb indices ofG′ is(33)M1G′=∑u∈VG′du2=82+82+82+⋯+82=9⋅82=36⋅42,M2G′=∑uv∈EG′dudv=8⋅8+8⋅8+8⋅8+⋯+8⋅8=36⋅82=36⋅43.Figure 2
Affine plane of order 3.Figure 3
Corresponding triangle for the linel1 of the affine plane of order 3.Figure 4
The8-regular graph obtained from the affine plane of order 3.Example 4.
Let us take the affine plane of order 4 with points and lines given, respectively:(34)P″=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,ℒ″=l1=1,2,3,4,l2=5,6,7,8,l3=9,10,11,12,l4=13,14,15,16,l5=1,5,9,13,l6=2,6,10,14,l7=3,7,11,15,l8=4,8,12,16,l9=1,6,11,16,l10=2,5,12,15,l11=3,8,9,14,l12=4,7,10,13,l13=1,7,12,14,l14=2,8,11,13,l15=3,5,10,16,l16=4,6,9,15,l17=1,8,10,15,l18=2,7,9,16,l19=3,6,12,13,l20=4,5,11,14.
With the method given earlier, we know thatVG=P. Every given line li=li1,li2,…,lik in this affine plane of order 4 consists of 4 elements. So, k is 4 in every step of obtaining sli. In other words, every line of this affine plane is considered as an ordered 4-gon, which is denoted as C4 in graph theory. The vertex and edge sets of the graph G″ that is obtained from the affine plane of order 4 are as follows:(35)VG″=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,EG″=l1,1=1,2,l1,2=2,3,l1,3=3,4,l1,4=4,1,l2,1=5,6,l2,2=6,7,l2,3=7,8,l2,4=8,5,l3,1=9,10,l3,2=10,11,l3,3=11,12,l3,4=12,9,l4,1=13,14,l4,2=14,15,l4,3=15,16,l4,4=16,13,l5,1=1,5,l5,2=5,9,l5,3=9,13,l5,4=13,1,l6,1=2,6,l6,2=6,10,l6,3=10,14,l6,4=14,2,l7,1=3,7,l7,2=7,11,l7,3=11,15,l7,4=15,3,l8,1=4,8,l8,2=8,12,l8,3=12,16,l8,4=16,4,l9,1=1,6,l9,2=6,11,l9,3=11,16,l9,4=16,1,l10,1=2,5,l10,2=5,12,l10,3=12,15,l10,4=15,2,l11,1=3,8,l11,2=8,9,l11,3=9,14,l11,4=14,3,l12,1=4,7,l12,2=7,10,l12,3=10,13,l12,4=13,4,l13,1=1,7,l13,2=7,12,l13,3=12,14,l13,4=14,1,l14,1=2,8,l14,2=8,11,l14,3=11,13,l14,4=13,2,l15,1=3,5,l15,2=5,10,l15,3=10,16,l15,4=16,3,l16,1=4,6,l16,2=6,9,l16,3=9,15,l16,4=15,4,l17,1=1,8,l17,2=8,10,l17,3=10,15,l17,4=15,1,l18,1=2,7,l18,2=7,9,l18,3=9,16,l18,4=16,2,l19,1=3,6,l19,2=6,12,l19,3=12,13,l19,4=13,3,l20,1=4,5,l20,2=5,11,l20,3=11,14,l20,4=14,4,where G″ is a graph and has 16 vertex and 80 edges. If we determine the vertex degrees for each vertex, we obtain(36)d1=d2=d3=d4=d5=d6=d7=10,d8=d9=d10=d11=d12=d13=d14=d15=d16=10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10=1016.
Thus,G″ is a 10-regular graph with the degree sequence as above. The adjacency matrix for G′′ is given below:(37)AG″=0101111100001111101011110000111101011111000011111010111100001111111101011111000011111010111100001111010111110000111110101111000000001111010111110000111110101111000011110101111100001111101011111111000011110101111100001111101011110000111101011111000011111010,where G″ has spectrum 10,−6,22,−24,08 and the energy of G″ is EG″=28. See Figure 5.
The Wiener index ofG″ is(38)WG″=12∑u∈VG″dG″u=12⋅1⋅10+2⋅5+1⋅10+2⋅5+⋯+1⋅10+2⋅5=12⋅20⋅16=160.
Zagreb indices ofG″ is(39)M1G″=∑u∈VG″du2=102+102+102+⋯+102=16⋅102=64⋅52,M2G″=∑uv∈EG″dudv=10⋅10+10⋅10+10⋅10+⋯+10⋅10=80⋅102=64⋅53.
When we obtain the affine graph for the affine plane of order 5, the affine graph of order 5, we calculate it as 25 vertex and 150 edges, and it is 12-regular. The adjacency matrix for this graph is given below.
The Wiener index for affine graph of order 5, namely,G‴ is(40)WG‴=12∑u∈VG‴dG‴u=12⋅1⋅12+2⋅12+1⋅12+2⋅12+⋯+1⋅12+2⋅12=12⋅36⋅25=450.
Zagreb indices ofG‴ is(41)M1G‴=∑u∈VG‴du2=122+122+122+⋯+122=25⋅122=100⋅62,M2G‴=∑uv∈EG‴dudv=12⋅12+12⋅12+12⋅12+⋯+12⋅12=150⋅122=100⋅63,AG‴=0100111111000000000011111101001111100000000001111101010111110000000000111110010111111000000000011111100101111100000000001111111111010011111100000000001111110100111110000000000111110101011111000000000011111001011111100000000001111110010111110000000000000001111101001111110000000000111111010011111000000000011111010101111100000000001111100101111110000000000111111001011111000000000000000111110100111111000000000011111101001111100000000001111101010111110000000000111110010111111000000000001111100101111111111000000000011111010011111100000000001111110100111110000000000111110101011111000000000011111001011111100000000001111110010.
Also, it has spectrum12,−1/2+55/22,−1/2+5/210,−1/2−5/210,−1/2−55/22 and the energy of this graph is 12+205.
The results regarding the spectra and energies of affine graphs are consistent with the lower and upper boundaries, given for regular graphs in [8–10].Figure 5
The10-regular graph obtained from the affine plane of order 4.Corollary 3.
Affine graphs of orderk consist of k2 vertices and k2+kk=k3+k2 edges.Now, we give a theorem and a corollary for the characterization of the graphs that are obtained from affine planes.Theorem 2.
Affine graphs of orderk for k≥3 are 2k+1-regular and has the degree sequence in the following form:(42)2k+1,2k+1,…,2k+1=2k+1k2.Proof.
LetA=P,ℒ be an affine plane of order k for k≥3 and the graph G=V,E is obtained from A.
We know that, in affine planes of orderk, all lines has k points and every point is exactly on k+1 distinct lines. As mentioned just before Theorem 1 for a point lir on a line li=li1,li2,…,lik, there are exactly two edges li,r−1 and li,r for that li.
The pointlir is on exactly k+1 distinct lines, so if it is incident with two edges for every line, then we have 2k+1 edges incident with the vertex lir.
Therefore, every vertex inG has the degree 2k+1. There are k2 vertices in G since VG=P and P=k2. Thus, we have(43)2k+1,2k+1,…,2k+1=2k+1k2,as the degree sequence.Theorem 3.
LetG be an affine graphs of order k for 3≤k≤5. The Wiener index for these graphs can be calculated as(44)WG=k+1⋅k−2⋅k2.Proof.
Proof can be done by following simple calculations.Theorem 4.
LetG be an affine graphs of order k for k≥3. Zagreb indices for these graphs can be calculated as(45)M1G=4⋅k2⋅k+12,M2G=4⋅k2⋅k+13.Proof.
Proof can be done by the following simple calculations.


## 2.1. The Method of Obtaining Graphs from Finite Affine Planes

In this part, a method will be presented to obtain a graph from a given finite affine plane. We note that obtaining a graphG=V,E from a finite affine plane A=P,ℒ, which itself is already a graph G=A, is pointless, but still the method we are going to introduce remains valid for such affine planes.Definition 4.
(1) LetA=P,ℒ be a finite affine plane of order k. If li is a line, then it must have k points. We take this line as an ordered k-tuple li=li1,li2,li3,…,lik. It is obvious that k≥2. We establish a new set “sli” for any line li=li1,li2,li3,…,lik in A such that if k=2, then li=li1,li2, and we define(9)sli≔li,and if k≥3, then first we define(10)li,j≔lij,lij+1,1≤j<k,lik,li1,j=k,and second(11)sli≔li,j|j=1,2,…,k≔li,1,li,2,li,3,…,li,k−1,li,k≔li1,li2,li2,li3,…,lik−1,lik,lik,li1.
Throughout this papersli is called as ordered k-gon corresponding to line li when k≥3.
If we try to obtain a graph from a finite affine planeA=P,ℒ, then we have to change our perception of lines. To do so, we use the method introduced in Definition 4.
Let us consider a lineli=li1,li2,li3,…,lik. If k≥3, for 1≤r≤k, any point lir is incident with only li,r−1 and li,r.
For a lineli=li1,li2,li3,…,lik, if k≥3, sli can be considered as a Ck. Also, we know that a C3 is often called a triangle, a C4 is a quadrilateral, a C5 is a pentagon, a C6 is a hexagon, and so on.
In the following theorem, we obtain a graph from a finite affine planeA of any order by considering every element of obtained sli for a line li, as an edge. It is obvious that every element of sli obtained from li is a set of exactly two points.Theorem 1.
IfA=P,ℒ is a finite affine plane of order k, then we have a graph G=V,E such that(12)VG=P,EG=∪li∈ℒsli.Proof.
For any lineli=li1,li2,li3,…,lik∈ℒ, it is trivial that li=k≥2 and every set li,j consists of exactly 2 vertices.
Letx,y∈VG=P be distinct elements. From (A1), there exists only one line(13)li=li1,li2,…,lik,passing through the points x and y. Therefore, for 1≤r,t≤k, there exists(14)x=lir,y=lit,in li. Since r≠t, we take r<t without loss of generality.
Whent = r + 1, there is an edge,(15)li,r=lir,lir+1=lir,lit=x,y,incident with x and y. In other words, when t=r+1, there is only one edge passing through x and y and that is li,r.
Whent>r+1 if t=k and r=1, then there is an edge,(16)li,k=lik,li1=lit,lir=y,x,incident with y and x. In other words, when t>r+1 if t=k and r=1, there is only one edge passing through y and x and that is li,k.
In other cases, it is obvious from the construction ofsli that there is no edge incident with x and y. Thus, we show that G=V,E is a graph.
Throughout this work, we are going to use the method introduced by Theorem1 to obtain a graph from a finite affine plane unless otherwise noted.
We should point out that we have already developed a new and different algorithm to create a new graph generating system from various incidence structures.Corollary 1.
IfA=P,ℒ is a finite affine plane of order k and the graph G=V,E is obtained from A, then EG=ℒ if and only if A is the smallest affine plane.Proof.
We know that if graphG=V,E is obtained from A, then(17)VG=P,EG=∪li∈ℒsli.
Firstly, let us assumeEG=ℒ. For every line li=li1,li2,…,lik of A, if k≠2, then we have an ordered k-gon corresponding to that li which causes a differentiation (an increase on the number of edges) between the number of edges of EG and the number of lines of ℒ. For that reason, k must be 2 for every line li=li1,li2,…,lik of A. It means that A is the affine plane of order 2 which is the smallest one.
Secondly, let us assumeA is the smallest affine plane. For every line li=li1,li2,…,lik of A, we know that k=2. From Definition 4, we always get the k=2 condition which implies for every line, and we get the result(18)sli=li.
SinceEG=∪li∈ℒsli, we obtain(19)EG=li|li∈ℒ=ℒ.Corollary 2.
For a graphG=V,E which is obtained from an affine plane A=P,ℒ,(20)EG=ℒ⇔G=A.Proof.
From Theorem1, we know that(21)VG=P,EG=∪li∈ℒsli.
IfEG=ℒ, then G=A since VG,EG=P,ℒ.
We found that(22)G=A⇒V,E=P,ℒ,⇒VG=P∧EG=ℒ,⇒EG=ℒ,since the equality of ordered pairs dictates one by one equality.
If there were no conditionVG=P in Theorem 1, then the equality of EG and ℒ would not imply the equality of G and A.Definition 5.
A graph obtained from an affine planeA of order k is called as “affine graph of order k corresponding to A,” or if there will not be any confusion, “affine graph of order k ” can be used.
Now, we will examine how affine graphs are obtained when the affine plane of order 2 and the affine plane of order 3 is taken asA=P,ℒ.Example 2.
We are going to investigate the graph obtained from the smallest affine plane given in Example1.
In this situation, as a result of Corollary1 and Corollary 2, we do not need to make any further arrangement for the set of the points and lines because the smallest affine plane is also a graph itself:(23)VG=1,2,3,4=P,EG=l1=1,2,l2=3,4,l3=1,3,l4=2,4,l5=1,4,l6=2,3=ℒ,where G=V,E is a graph and has 4 vertex and 6 edges. If we determine the vertex degrees for each vertex, we obtain(24)d1=d2=d3=d4=3,3,3,3,3=34.
Thus,G is a 3-regular graph (cubic graph) with the degree sequence as above.
Adjacency matrix forG is given below:(25)AG=0111101111011110,where G has spectrum 3,−13 and the energy of G is EG=6.
The Wiener index ofG is(26)WG=12∑u∈VGdGu=12⋅3+3+3+3=6.
Zagreb indices ofG is(27)M1G=∑u∈VGdu2=32+32+32+32=4⋅32=36,M2G=∑uv∈EGdudv=3⋅3+3⋅3+3⋅3+3⋅3+3⋅3+3⋅3=6⋅32=54.Example 3.
Let us take the affine plane of order 3 with points and lines given, respectively,(28)P′=1,2,3,4,5,6,7,8,9,ℒ′=l1=1,2,3,l2=4,5,6,l3=7,8,9,l4=1,4,7,l5=2,5,8,l6=3,6,9,l7=1,5,9,l8=2,6,7,l9=3,4,8,l10=3,5,7,l11=1,6,8,l12=2,4,9,and illustrated by Figure 2.
With the method given earlier, we know thatVG=P. Every given line li=li1,li2,…,lik in this affine plane of order 3 consists of 3 elements. So, k is 3 in every step of obtaining sli. In other words, every line of this affine plane considered as an ordered 3-gon which is denoted as C3 in graph theory. See Figure 3.
The vertex and edge sets of the graphG′ that is obtained from the affine plane of order 3 are as follows:(29)VG′=1,2,3,4,5,6,7,8,9,EG′=l1,1=1,2,l1,2=2,3,l1,3=3,1,l2,1=4,5,l2,2=5,6,l2,3=6,4,l3,1=7,8,l3,2=8,9,l3,3=9,7,l4,1=1,4,l4,2=4,7,l4,3=7,1,l5,1=2,5,l5,2=5,8,l5,3=8,2,l6,1=3,6,l6,2=6,9,l6,3=9,3,l7,1=1,5,l7,2=5,9,l7,3=9,1,l8,1=2,6,l8,2=6,7,l8,3=7,2,l9,1=3,4,l9,2=4,8,l9,3=8,3,l10,1=3,5,l10,2=5,7,l10,3=7,3,l11,1=1,6,l11,2=6,8,l11,3=8,1,l12,1=2,4,l12,2=4,9,l12,3=9,2,where G′ is a graph and has 9 vertex and 36 edges. If we determine the vertex degrees for each vertex, we obtain(30)d1=d2=d3=d4=d5=d6=d7=d8=d9=8,8,8,8,8,8,8,8,8,8=89.
Thus,G′ is a 8-regular graph with the degree sequence as above. Adjacency matrix for G′ is given below:(31)AG′=011111111101111111110111111111011111111101111111110111111111011111111101111111110,where G′ has spectrum 8,−18 and the energy of G′ is EG′=16. See Figure 4.
The Wiener index ofG′ is(32)WG′=12∑u∈VG′dG′u=12⋅8+8+8+⋯+8=36.
Zagreb indices ofG′ is(33)M1G′=∑u∈VG′du2=82+82+82+⋯+82=9⋅82=36⋅42,M2G′=∑uv∈EG′dudv=8⋅8+8⋅8+8⋅8+⋯+8⋅8=36⋅82=36⋅43.Figure 2
Affine plane of order 3.Figure 3
Corresponding triangle for the linel1 of the affine plane of order 3.Figure 4
The8-regular graph obtained from the affine plane of order 3.Example 4.
Let us take the affine plane of order 4 with points and lines given, respectively:(34)P″=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,ℒ″=l1=1,2,3,4,l2=5,6,7,8,l3=9,10,11,12,l4=13,14,15,16,l5=1,5,9,13,l6=2,6,10,14,l7=3,7,11,15,l8=4,8,12,16,l9=1,6,11,16,l10=2,5,12,15,l11=3,8,9,14,l12=4,7,10,13,l13=1,7,12,14,l14=2,8,11,13,l15=3,5,10,16,l16=4,6,9,15,l17=1,8,10,15,l18=2,7,9,16,l19=3,6,12,13,l20=4,5,11,14.
With the method given earlier, we know thatVG=P. Every given line li=li1,li2,…,lik in this affine plane of order 4 consists of 4 elements. So, k is 4 in every step of obtaining sli. In other words, every line of this affine plane is considered as an ordered 4-gon, which is denoted as C4 in graph theory. The vertex and edge sets of the graph G″ that is obtained from the affine plane of order 4 are as follows:(35)VG″=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,EG″=l1,1=1,2,l1,2=2,3,l1,3=3,4,l1,4=4,1,l2,1=5,6,l2,2=6,7,l2,3=7,8,l2,4=8,5,l3,1=9,10,l3,2=10,11,l3,3=11,12,l3,4=12,9,l4,1=13,14,l4,2=14,15,l4,3=15,16,l4,4=16,13,l5,1=1,5,l5,2=5,9,l5,3=9,13,l5,4=13,1,l6,1=2,6,l6,2=6,10,l6,3=10,14,l6,4=14,2,l7,1=3,7,l7,2=7,11,l7,3=11,15,l7,4=15,3,l8,1=4,8,l8,2=8,12,l8,3=12,16,l8,4=16,4,l9,1=1,6,l9,2=6,11,l9,3=11,16,l9,4=16,1,l10,1=2,5,l10,2=5,12,l10,3=12,15,l10,4=15,2,l11,1=3,8,l11,2=8,9,l11,3=9,14,l11,4=14,3,l12,1=4,7,l12,2=7,10,l12,3=10,13,l12,4=13,4,l13,1=1,7,l13,2=7,12,l13,3=12,14,l13,4=14,1,l14,1=2,8,l14,2=8,11,l14,3=11,13,l14,4=13,2,l15,1=3,5,l15,2=5,10,l15,3=10,16,l15,4=16,3,l16,1=4,6,l16,2=6,9,l16,3=9,15,l16,4=15,4,l17,1=1,8,l17,2=8,10,l17,3=10,15,l17,4=15,1,l18,1=2,7,l18,2=7,9,l18,3=9,16,l18,4=16,2,l19,1=3,6,l19,2=6,12,l19,3=12,13,l19,4=13,3,l20,1=4,5,l20,2=5,11,l20,3=11,14,l20,4=14,4,where G″ is a graph and has 16 vertex and 80 edges. If we determine the vertex degrees for each vertex, we obtain(36)d1=d2=d3=d4=d5=d6=d7=10,d8=d9=d10=d11=d12=d13=d14=d15=d16=10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10=1016.
Thus,G″ is a 10-regular graph with the degree sequence as above. The adjacency matrix for G′′ is given below:(37)AG″=0101111100001111101011110000111101011111000011111010111100001111111101011111000011111010111100001111010111110000111110101111000000001111010111110000111110101111000011110101111100001111101011111111000011110101111100001111101011110000111101011111000011111010,where G″ has spectrum 10,−6,22,−24,08 and the energy of G″ is EG″=28. See Figure 5.
The Wiener index ofG″ is(38)WG″=12∑u∈VG″dG″u=12⋅1⋅10+2⋅5+1⋅10+2⋅5+⋯+1⋅10+2⋅5=12⋅20⋅16=160.
Zagreb indices ofG″ is(39)M1G″=∑u∈VG″du2=102+102+102+⋯+102=16⋅102=64⋅52,M2G″=∑uv∈EG″dudv=10⋅10+10⋅10+10⋅10+⋯+10⋅10=80⋅102=64⋅53.
When we obtain the affine graph for the affine plane of order 5, the affine graph of order 5, we calculate it as 25 vertex and 150 edges, and it is 12-regular. The adjacency matrix for this graph is given below.
The Wiener index for affine graph of order 5, namely,G‴ is(40)WG‴=12∑u∈VG‴dG‴u=12⋅1⋅12+2⋅12+1⋅12+2⋅12+⋯+1⋅12+2⋅12=12⋅36⋅25=450.
Zagreb indices ofG‴ is(41)M1G‴=∑u∈VG‴du2=122+122+122+⋯+122=25⋅122=100⋅62,M2G‴=∑uv∈EG‴dudv=12⋅12+12⋅12+12⋅12+⋯+12⋅12=150⋅122=100⋅63,AG‴=0100111111000000000011111101001111100000000001111101010111110000000000111110010111111000000000011111100101111100000000001111111111010011111100000000001111110100111110000000000111110101011111000000000011111001011111100000000001111110010111110000000000000001111101001111110000000000111111010011111000000000011111010101111100000000001111100101111110000000000111111001011111000000000000000111110100111111000000000011111101001111100000000001111101010111110000000000111110010111111000000000001111100101111111111000000000011111010011111100000000001111110100111110000000000111110101011111000000000011111001011111100000000001111110010.
Also, it has spectrum12,−1/2+55/22,−1/2+5/210,−1/2−5/210,−1/2−55/22 and the energy of this graph is 12+205.
The results regarding the spectra and energies of affine graphs are consistent with the lower and upper boundaries, given for regular graphs in [8–10].Figure 5
The10-regular graph obtained from the affine plane of order 4.Corollary 3.
Affine graphs of orderk consist of k2 vertices and k2+kk=k3+k2 edges.Now, we give a theorem and a corollary for the characterization of the graphs that are obtained from affine planes.Theorem 2.
Affine graphs of orderk for k≥3 are 2k+1-regular and has the degree sequence in the following form:(42)2k+1,2k+1,…,2k+1=2k+1k2.Proof.
LetA=P,ℒ be an affine plane of order k for k≥3 and the graph G=V,E is obtained from A.
We know that, in affine planes of orderk, all lines has k points and every point is exactly on k+1 distinct lines. As mentioned just before Theorem 1 for a point lir on a line li=li1,li2,…,lik, there are exactly two edges li,r−1 and li,r for that li.
The pointlir is on exactly k+1 distinct lines, so if it is incident with two edges for every line, then we have 2k+1 edges incident with the vertex lir.
Therefore, every vertex inG has the degree 2k+1. There are k2 vertices in G since VG=P and P=k2. Thus, we have(43)2k+1,2k+1,…,2k+1=2k+1k2,as the degree sequence.Theorem 3.
LetG be an affine graphs of order k for 3≤k≤5. The Wiener index for these graphs can be calculated as(44)WG=k+1⋅k−2⋅k2.Proof.
Proof can be done by following simple calculations.Theorem 4.
LetG be an affine graphs of order k for k≥3. Zagreb indices for these graphs can be calculated as(45)M1G=4⋅k2⋅k+12,M2G=4⋅k2⋅k+13.Proof.
Proof can be done by the following simple calculations.


## 3. Conclusion

With this study, we start giving some relations between the incidence structures and graph theory from our new perspective. It is easily seen that there are some differences and similarities between the affine graphs of orderk and the affine planes of order k, although the relations between them have not been examined thoroughly yet.There are also some open problems in this subject that we are constantly studying on and which we think we are going to be able to examine and answer in the future. Some of them are in the following paragraphs.We know that it is possible to obtainprojective graphs as the geometric structure shift to projective planes, from [11] and more from [12]. What is the relation between affine and projective graphs which have the same order? For example, how does the existence and absence of the parallel axiom in affine and projective planes affect the graphs that are obtained from these planes?We know that an affine plane is obtained when a line, with the points, is thrown away from a projective plane. Under which conditions can we find an affine graph of orderk by deleting a Ck+1, with the vertices, from a projective graph of order k?We know that affine planes of orderk can be embedded into projective planes of order k. Can affine graphs of order k be embedded in projective graphs of order k?How can we determine whether a given graph is an affine graph?Is there a relation between the isomorphism of geometric structures and associated graphs?How can we determine the chromatic index of affine graphs? Is there a relationship between the parallel groups of affine planes and the chromatic index of corresponding affine graphs?



---

*Source: 9983771-2021-05-04.xml*