On the Line Graph of the Complement Graph for the Ring of Gaussian Integers Modulo n ()
1. Introduction
The line graph
of a graph
is defined to be the graph whose vertex set constitutes of the edges of
, Where two vertices are adjacent if the corresponding edges have a common vertex in
. The importance of line graphs stems from the fact that the line graph transforms the adjacency relations on edges to adjacency relations on vertices. For example, the chromatic index of a graph leads to the chromatic number of its line graph. The zero divisor graph of a commutative ring
, denoted by
, is defined as the graph whose vertex set is the set of all non-zero zero divisors of
and edge set
. This type of graphs provides an example showing that algebraic methods could be applied to problems about graphs. The set of Gaussian integers, denoted by
, is defined as the set of complex numbers
, where
. If
is a prime Gaussian integer, then
is either 1)
or
, or 2) q where q is a prime integer and
, or 3)
,
where
,
is a prime integer and
.
Throughout this paper,
and
denote prime integers which are congruent to 1 modulo 4, while
and and
denote prime integers which are congruent to 3 modulo 4. All rings in this paper are assumed to be commutative with unity. The zero divisor graph for the ring of Gaussian integers modulo
is studied in [1] and [2], the complement of this graph is discussed in [3]. While the line graph of the zero divisor graph for the ring of Gaussian integers modulo n is investigated in [4]. In this paper it should be kept in mind that
, and hence, its line graph is
,
is an integral domain, so
. Further,
is a complete graph whose complement is totally disconnected and thus its line graph is
. While
, so its complement is disconnected with two components each of which is isomorphic to
. Finally, note that the graph
is bipartite, [1] and
.
In this paper, we investigate properties of the graph
. We find the diameter, the radius of
. We determine which
is Eulerian, Hamiltonian, regular, locally
, locally connected or planer. Furthermore, the chromatic index and the edge domination number of
where
is a power of a prime are computed. While the domination number of
is given. On the other hand, a formula which gives the degree of each vertex in
is derived, thus the degree of its complement as well as its line graph could easily be found.
2. When Is
Eulerian or Planner
If
is a connected graph. Then
is Eulerian if and only if every vertex of
has even degree. For a finite ring
, the line graph
of a connected graph
is Eulerian if and only if all vertices of
have the same parity ( see the proof of Lemma 3.10, [5]). On the other hand, if
has both even and odd vertices, then so is its complement. So, for a connected graph
, the graph
is Eulerian if and only if all vertices in
are either even or all vertices in
are all odd. But
is connected if
[3] and
is Eulerian if
or
is a product of distinct odd primes [1]. It is easy to show that all vertices of
are odd if and only if
. This proves the following theorem.
Theorem 2.1
is Eulerian if and only if
is a product of distinct odd primes.
A planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints.
Next we determine when the graph
is planar.
In a graph
the maximum vertex degree and the minimum vertex degree will be denoted by
and
, respectively.
The following theorem characterizes graphs
whose line graph
is planer.
Theorem 2.2 [6]
A nonempty graph
has a planer line graph
if and only if 1)
is planer.
2)
, and 3) if
, then
is a cut vertex.
The graph
is planer if and only if ![](https://www.scirp.org/html/6-1200046\c8b488ef-fd64-438e-8f5a-504ec27b1efa.jpg)
or
[3]. For
,
,
. While for
,
, this graph is regular of degree 3.
Thus we obtain the following.
Theorem 2.3 The graph
is planer if and only is
.
3. The Diameter of ![](https://www.scirp.org/html/6-1200046\fac76310-e2ca-43a2-a15a-afe6a2cd6c80.jpg)
For a connected graph
, the distance,
, between two vertices
and
is the minimum of the lengths of all
paths of
. The eccentricity of a vertex
in
is the maximum distance from
to any vertex in
. The diameter of
,
, is the maximum eccentricity among the vertices of
. Since
is connected if
and each of
and
is the union of two complete graphs, while
and
are the union of a nullgraph and a connected graph [3], we have the following.
Theorem 3.1
is connected if and only if
.
Theorem 3.2 If
or
, then
.
Proof. 1) Assume that
and
![](https://www.scirp.org/html/6-1200046\bc06b421-86a4-4229-a299-25aa62599fd6.jpg)
are two nonadjacent vertices in
. Since for every
,
and
are both even or odd [1], we have three cases:
Case I: for
,
and
are odd. Then we have the path
.
Case II: for
,
or
is odd(even) and
or
is even (odd). Assume that
are even and
are odd. Then we have the path
.
Case III: for
,
and
are even.
Then
and
where ![](https://www.scirp.org/html/6-1200046\81816afd-635f-46e0-b90c-7355a29b769a.jpg)
are odd and
for
. If
or
, say
, then
or
, say
.
So, we have the path
. Now suppose that
is odd. Then a) If
, for
or 2, say for
, then
or
, say
. Hence, we have the path
.
b) If
or
and
, for
or 2, say for
, then we have a path
or
.
c) If
, for
or 2, say for
, then
implies that
. Otherwise
or
. Then we have a path
or
.
2) Assume that
and
![](https://www.scirp.org/html/6-1200046\91238801-6152-4065-9922-72efdf6812e5.jpg)
Then
or
, say
. Hence
or
, say
. Then we have the path
. ![](https://www.scirp.org/html/6-1200046\8b67c2ff-f13f-406f-ae89-7e052fb2a6fa.jpg)
Theorem 3.3 Let
be a ring that is a product of two rings
and
with at least one of them is not ID with more than one regular element and the other has more than two regular elements. Then
.
Proof. Suppose that
and
is not ID,
and
. Let
and
. Clearly,
in
. So,
. Now, let
then
or
and
or
. So, we have three cases:
Case I:
and
. Then
implies that
.
And
or
, say
implies that
![](https://www.scirp.org/html/6-1200046\b921d57c-9ce9-4063-8bb6-e6b4eb7c1bb2.jpg)
where
.
Case II:
and
. Then there exists
and hence
.
Case III:
and
or
and
. Let
and
. Then
implies that
and
or
.
And if
, then
or
and
or
. ![](https://www.scirp.org/html/6-1200046\78add2ba-fb61-4add-bb7f-5ac325da9d50.jpg)
For
,
[7] and for
with
,
.
Moreover
and
for
. An immediate consequence of Theorem 3.3 is the following.
Theorem 3.4 Let
or n is a composite such that
. Then
.
4. The Radius and the Girth of the Graph ![](https://www.scirp.org/html/6-1200046\11491a49-1fae-45a2-8301-02634d87a1ef.jpg)
For a connected graph
, the radius of
,
, is the minimum eccentricity among the vertices of
. So,
. Since for any
,
and
are non adjacent,
. Using Theorem 3.2 gives for
or
,
.
Theorem 4.1 If
or
where
,
is prime integer,
and
then
.
Proof. Since
to show that
it is enough to find a vertex
with eccentricity 2. If
, then
for every
. So
.
Now, assume that
and
.
Then we have four cases:
Case I:
. Then
.
Case II:
. Then
.
Case III:
and
. Then
and hence there exists
. So,
.
Case IV:
. Then
. ![](https://www.scirp.org/html/6-1200046\9402cf0d-fbff-435f-aaac-748aed7dc2b5.jpg)
Theorem 4.2
if and only if
or
.
Vising [8], proved that for a connected simple graph
with n-vertices and radius 2, the upper bound of the number of edges of
is
. Then Golberg [9]
proved that the lower bound of numbers of edges of a simple connected graph
with radius 2 is
.
So we can conclude the following.
Theorem 4.3 For
or
,
implies that
.
The girth of a graph
,
is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles (i.e.. it’s an acyclic graph), its girth is defined to be infinity. If
is a cycle of length three in
. Then
is a cycle of length 3 in
. So,
whenever
. In [3] it is proved that the girth of
equals 3 for
. So, we have the following.
Theorem 4.4 For
,
.
5. The Locally Connected Property of the Graphs
and ![](https://www.scirp.org/html/6-1200046\f1ee045b-84d4-4660-841f-8890c4a40013.jpg)
We say that a vertex
is locally connected if the neighborhood of
,
, is connected; and
is locally connected if every vertex of
is locally connected.
Theorem 5.1 If
for
and either
or
is not ID, then
is locally connected.
Proof. Suppose that
is not ID and
. Then we have two cases:
Case I:
or
. If
, then there exists
. So
for all
. And if
, then there exists
such that
. Therefore,
for every
. So
is connected.
Case II:
and
. Then there exist
,
and
such that
and
. Moreover,
. And for every
,
or
. So
is connected. ![](https://www.scirp.org/html/6-1200046\55d8a75e-8415-4751-8b54-feef27c54f5b.jpg)
Theorem 5.2 If
for
and either
or
is not ID, then
is locally connected.
Proof. Suppose that
is not ID, ![](https://www.scirp.org/html/6-1200046\b06bc6b4-28b8-4b51-bf9a-17cf7df2bc7a.jpg)
and
, then we have three cases:
Case I:
. Then
.
Case II:
. If
, then
.
Otherwise there exists
. So,
.
Case III:
or
. Assume that
, then
implies that there exists
satisfies
.
While
implies that that there exists
satisfies
. ![](https://www.scirp.org/html/6-1200046\ed9e301e-e7de-44b1-bf01-c678ac65076e.jpg)
From Theorem 5.1 and Theorem 5.2 we conclude the following.
Theorem 5.3 If
or
is a composite integer such that
, then both
and
are locally connected.
6. When Is
Hamiltonian?
A Hamiltonian cycle is a cycle that visits each vertex exactly once (except the vertex which is both the start and end, and so is visited twice). A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. The line graph of a graph
with more than 4 vertices and diameter 2 is Hamiltonian [10]. But
is disconnected with one isolated vertex
and the other component, call this component
, with diameter 2 [3]. So,
. Similarly,
has a connected subgraph
with diameter 2 and
. Hence, the following result is obtained.
Theorem 6.1 If
or
, then
is Hamiltonian.
Oberly and Sumner [11] proved that every connected, locally connected claw free graph (i.e. it does not contain a complete bipartite graph
) is hamiltonian. Since the line graph is claw free, using Theorem 5.3, we get the following.
Theorem 6.2 If
or
is a composite integer such that
, then
is hamiltonian.
7. The Chromatic Number of the Graph ![](https://www.scirp.org/html/6-1200046\6ed8cde0-027e-4b63-a2f5-e9689c470a31.jpg)
The edge coloring of a graph
is an assignment of colors to the edges of the graph so that no two adjacent edges have the same color. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph denoted by
.
Lemma 7.1 [12]
If
has order
and
, then
.
Theorem 7.2 If
, then
.
Proof. Note that in
, the induced subgraph,
, with
is connected,
, [1] and
. Since the vertex
is adjacent to all other vertices in
, we have
. Using Lemma 6.1,
. ![](https://www.scirp.org/html/6-1200046\965f29ea-3e45-44d0-acec-8e8c92cc8787.jpg)
Since
is empty graph and
is edgeless with
vertices, we consider the case
.
Theorem 7.3 If
, then
![](https://www.scirp.org/html/6-1200046\9511e54c-5128-4e50-8da2-a2e860f57971.jpg)
Proof. Let ![](https://www.scirp.org/html/6-1200046\fb33adae-57e3-401b-a037-bcb78ddb25aa.jpg)
Then
is the set of all isolated vertices in
.
So the induced subgraph,
, with the vertices
is a connected graph,
. Clearly the vertex
is adjacent to all other vertices in
and hence,
. Using Lemma 7.1,
![](https://www.scirp.org/html/6-1200046\6d7789aa-8365-4284-8f34-f2e5c402a6fe.jpg)
![](https://www.scirp.org/html/6-1200046\f3f510e6-3f53-4a7e-84a3-a4c6e1c4daeb.jpg)
Finally we find the chromatic index of
.
A subset
of the vertex set
is said to be independent if no two vertices in this set are adjacent. A clique of a graph is a maximal complete subgraph. A graph
is said to be split if it’s vertex set can be partitioned into two subsets
and
such that
induces a clique and
is independent in
.
Lemma 7.4 [13] Let
be a split graph. If
is odd, then
.
Theorem 7.5 If
, then
.
Proof. Since
, it is enough to find
. First, we’ll show that
is a split graph. Let
![](https://www.scirp.org/html/6-1200046\73c8f5b3-7a51-4277-a874-d9d18c5509ae.jpg)
.
Clearly,
,
induces a clique and
is independent. Therefore,
is a split graph. Moreover,
![](https://www.scirp.org/html/6-1200046\ba4b4925-cf4d-4500-a4fc-5ab191cae747.jpg)
is odd. From Lemma 7.4,
. ![](https://www.scirp.org/html/6-1200046\41f343d2-befc-458c-baac-2dada299bfdb.jpg)
A graph
is said to be critical if
is connected and
and for every edge
of
, we have
. The well-known Vizing’s theorem states that for a simple graph
,
or
.
Lemma 7.6 [14]
If
is a critical graph, then
has at least
of vertices of maximum degree.
Therefore, if
is a simple graph such that for every vertex
of maximum degree there exists an edge
such that
is more than the number of vertices with maximum degree in
, we have
[13].
Theorem 7.7 If
, then
.
Proof. Let
and
.
Then the vertices of
with maximum degree have the form
or
where
and
and
![](https://www.scirp.org/html/6-1200046\142ec4ea-31ed-4588-8578-37ab9bfccd4f.jpg)
and
![](https://www.scirp.org/html/6-1200046\134af19d-f290-40c1-9e88-67899ca94a90.jpg)
So,
. And the vertices of
with minimum degree have the form
or
where
and
. So
.
Therefore,
.
But the graph
has only
vertices of maximum degree. So,
.
Since
, the result holds. ![](https://www.scirp.org/html/6-1200046\0648807c-23aa-452c-8ff5-ba192e31768f.jpg)
Since the edge coloring of any graph leads to a vertex coloring of its line graph, we obtain the following.
Corollary 7.8 1) If
, then
.
2) If
, then
.
3) If
, then
.
8. The Domination Number of ![](https://www.scirp.org/html/6-1200046\82fe665f-89c9-47d6-b11f-d20918cba4f8.jpg)
A subset
of the vertex set
of a graph
is a dominating set in
if each vertex of
, not in
, is adjacent to at least one vertex of
. The minimum cardinality of all dominating sets in
,
, is called the domination number of
.
In
, the vertex
is an isolated vertex while the vertex
dominates all vertices in the second component. Therefore,
. The graph
thus
. In
the vertices
are isolated while the vertex
is adjacent to all other vertices in
so
. Since
![](https://www.scirp.org/html/6-1200046\1912aa4b-8609-4f97-8062-0f7a478074ed.jpg)
and
,
.
The set
is a minimum dominating set for
. And if
, where
, then
. This graph is connected and the set
is a minimum dominating set for
.
Theorem 8.1 1) If
, then
.
2)
and
![](https://www.scirp.org/html/6-1200046\760570f5-3e6f-4334-a513-80c2c8bcf7b9.jpg)
9. The Domination Number of ![](https://www.scirp.org/html/6-1200046\b575ea6f-eb6f-4f60-adbf-d812a22bcb67.jpg)
The independence number of
,
, is the maximum cardinality of all independent sets in
. A subset
of the edge set
of a graph
is an edge dominating set in
if each edge of
, not in
, is adjacent to at least one edge of
. The minimum cardinality of all edge dominating sets in
,
, is called the edge domination number of
. The minimum cardinality of all independent edge dominating sets,
, is called the independence edge domination number of
. The study of the domination number of the line graph of
leads to the study of edge or line domination number of
, i.e.
. On the other hand, for any graph
,
[15].
If
is an independent set in
, then
induces a complete graph in
. While if
induces a complete graph in
, then it is independent in
. Recall that
[2]. Then the sets,
,
form a partition for the set
. Clearly, the set
is the maximum independent set in
, while the set
induces a maximum complete subgraph in
. There are some edges joining
to
, no other adjacency exists in
. Any edge dominating set for
must contain at least
element in order to dominate
. On the other hand, this dominating set for
dominates all other edges in
. Since
, then
and
, could easily be computed to get the following theorem.
Theorem 9.1 For
.
1)
.
2)
.
3) ![](https://www.scirp.org/html/6-1200046\fb86a3f3-1ca4-4698-9c1c-db88f21a765d.jpg)
To study the graph
, consider the partition of
given by
![](https://www.scirp.org/html/6-1200046\ea6c7b7d-079f-4910-89e7-0643c6c39487.jpg)
and not both
. The set
is the maximum independent set, while
induces a maximum complete subgraph in
. There are some edges joining
to
, and
has no other adjacency. Easy calculations give
when
,
and
when
. While
and
.
Thus we obtain the following theorem.
Theorem 9.2 If
, then 1)
.
2)
if
is even and
if
is odd.
3) ![](https://www.scirp.org/html/6-1200046\ba0e5718-9c29-4dc2-8085-77584e42a352.jpg)
Now, we move to the case
. Let
.
Clearly, the sets
where
and not both
or 0, partition the vertices of
and
. Let
![](https://www.scirp.org/html/6-1200046\b9267d8e-0d07-4596-af51-9de38f782f9c.jpg)
Note that
induces a complete graph in
. Vertices in
are adjacent to all vertices except some vertices in
. Similarly, vertices in
are adjacent to all vertices except some vertices in
, and vertices in
are adjacent to all vertices except vertices in
. On the other hand
induces a complete subgraph and vertices in this set are adjacent to all other vertices except those of
. Clearly
induces a complete subgraph. Vertices in
form an independent set, and are adjacent to some vertices in
. Each of
and
induces a complete subgraph and are adjacent to some vertices in
. Besides, there are some edges between
and
. On the other hand,
![](https://www.scirp.org/html/6-1200046\83e2c631-bd93-4a40-9370-8793afe95256.jpg)
The above argument shows that
![](https://www.scirp.org/html/6-1200046\0c512b53-bcfd-4c86-8ce4-43700520767c.jpg)
10. The Degree of the Vertices in
and ![](https://www.scirp.org/html/6-1200046\79d1ac2d-f609-4c81-a392-923940d58f59.jpg)
Now, we determine the cardinality of the annihilator of the element
,
in
. This helps find the degree of each vertex in
, its complement, as well as the degree of each vertex in their corresponding line graphs.
Theorem 10.1 If
, then
where
.
Proof. Let
and
. Then
.
.
But
. So, ![](https://www.scirp.org/html/6-1200046\6ba54c76-0f86-44df-baf9-ed72c11e60a2.jpg)
and hence there exists
such that
.
Since
where
and the norm of
is less than the norm of
,
. By Theorem 2 of [7],
, so the result holds. ![](https://www.scirp.org/html/6-1200046\e40d8d69-37b6-4a80-aa06-2bf3c14d4220.jpg)
Theorem 10.2 Let
and
. Then
.
The order of
can be easily computed using formulas given in [1]. Thus we can find the degree of each vertex in the complement of
, here we give the degree of each vertex in the line graph of
, an analogous formula for the degree of vertices in
could be obtained.
Corollary 10.3 Let
,
and
. Then
.
Proof. Note that, for any graph
and
,
. ![](https://www.scirp.org/html/6-1200046\d9ef008f-fae8-4072-849f-11ace9748f33.jpg)
In the following we determine the degree of every vertex in the graphs
when
and
.
Theorem 10.4 Let
and
are odd. Then in
1)
.
2) ![](https://www.scirp.org/html/6-1200046\c063f965-83a2-4526-b8aa-c76b409ed0ca.jpg)
.
3)
.
Proof. 1) Note that,
if
or
and ![](https://www.scirp.org/html/6-1200046\0879e49d-75de-415e-9437-c00683445250.jpg)
if and only if
and
. Moreover
if and only if
.
2) Obvious.
3) Note that if
are odd, then
. ![](https://www.scirp.org/html/6-1200046\531e26a7-09f4-4ca0-a706-b76d63ff946c.jpg)
Theorem 10.5 Let
,
are relatively prime with
. Then in
,
.
Theorem 10.6 Let
,
and
. Then in
,
![](https://www.scirp.org/html/6-1200046\32fa6270-c0d4-4785-881e-e274597a0a42.jpg)
11. When is
,
Regular?
A graph
in which all vertices have the same degree is called regular graph.
Regularity of
was studied in [1]. However, we provide our own proof, since it comes as an immediate consequence of Theorem 10.2. Clearly, if
, then
is regular. If
or
, then the graph
has a vertex which is adjacent to all other vertices and it is not complete graph, thus
is not regular.
Now, we show that
is regular if and only if
.
Theorem 11.1 If
where
are distinct Gaussian primes and
and
, then
is not regular.
Proof. Choose two vertices
and
such that
, then
. So, the result follows. ![](https://www.scirp.org/html/6-1200046\268e0d95-8954-429e-8ea2-c00e93144826.jpg)
Next, we discuss regularity of the graph
and
. Clearly, if
is regular, then
is also regular, so if
, then the graph
is regular. On the other hand, if
is the complete bipartite graph
, then
for all vertices in
. Thus
is regular. While
is a bipartite graph with partite sets
and
![](https://www.scirp.org/html/6-1200046\04888507-acbb-4d43-89e4-c8dcd83e158d.jpg)
Moreover,
,
and
. Thus,
and hence,
is not regular.
Theorem 11.2 If
,
is a prime and
, then the graph
is not regular.
Proof. If
, then
If
, then
.
And if
,
,
, then
![](https://www.scirp.org/html/6-1200046\0e2cec1b-56bc-404a-bead-58e96ed66d3f.jpg)
![](https://www.scirp.org/html/6-1200046\cac0a798-70c2-41a2-b136-ae96994e17bf.jpg)
Theorem 11.3 Let
where
and
are commutative rings with unity with at least one of them is not ID. Then
is not regular.
Proof. Suppose that
is not ID and
, for
. Let
. If
, then
![](https://www.scirp.org/html/6-1200046\ee0e5446-75b6-4650-90c0-eeec6a5233e8.jpg)
and
if
, hence
. And if
,
![](https://www.scirp.org/html/6-1200046\70e63aa2-e3d4-4297-98cf-e34e9c00316d.jpg)
and
if
, hence
. But
. So
is not regular. ![](https://www.scirp.org/html/6-1200046\b743965f-f318-45f3-bad2-368adfdea864.jpg)
So as a consequence of Theorem 11.2 and Theorem 11.3, we conclude the following.
Theorem 11.4 The graph
is regular if and only if
.
Observe that, for
,
is the empty graph.
, so the line graph
is regular. While ![](https://www.scirp.org/html/6-1200046\a3f7722a-8772-477d-8621-fab079046ecd.jpg)
which is regular, so is
.
![](https://www.scirp.org/html/6-1200046\2fd3cccc-f220-41f4-92c5-3624f019532b.jpg)
![](https://www.scirp.org/html/6-1200046\59341072-b106-419d-b3c0-596adfb40e24.jpg)
And in
,
. So, the graph
is not regular for
,
is a prime and
.
Theorem 11.5 Let
where
and
are commutative rings with unity such that
,
for
. If ![](https://www.scirp.org/html/6-1200046\123df28e-b364-42ab-b4a2-5d7c4e650ad5.jpg)
and
, then
is not regular.
Proof. Since
, for
, there exist
and
. Therefore
. Since
,
.
So,
is not regular. ![](https://www.scirp.org/html/6-1200046\5da87f0b-2e33-43a0-bff6-b1cf874db308.jpg)
Theorem 11.6 The graph
is regular if and only if
or
.
12. When is
,
Locally H?
A simple graph
is said to be locally
if the neighborhood of each vertex in
induces the same graph
. The cartesian product
of two graphs
and
is the graph with vertex set
and two vertices in
are adjacent if and only if they are equal in one coordinate and adjacent in the other. Before we proceed, we give the following lemma.
Lemma 12.1 1) If
, then
is locally
.
2) If
, then
is locally
.
Proof. 1) Let
, then
![](https://www.scirp.org/html/6-1200046\4d84eca7-2a7b-44cb-a995-43acdd4fabd0.jpg)
each of the sets
and
induces a copy of
and since we deal with an undirected graphs, then for a fixed
,
and
are adjacent. Thus the result holds.
3) Let
, with partite sets
and
and with
,
. Then
.
Each set induces a complete graph
, respectively. And
has no other edges. Thus
induces
. ![](https://www.scirp.org/html/6-1200046\c73cf08d-a5db-46e1-beb3-84d5980fd898.jpg)
In order for a graph to be locally
, it should be regular graph. Thus for the graph
, it suffices to check the cases
, and for
, we consider only the cases
. Since
and
,
is locally
and
is locally
. In the same manner we can show that
is locally
,
is locally
and
is locally
.
Theorem 12.2 The following statements are equivalent.
1) The graph
is regular2) The graph
is locally
.