• No results found

Triangle-free projective-planar graphs with diameter two: Domination and characterization

N/A
N/A
Protected

Academic year: 2023

Share "Triangle-free projective-planar graphs with diameter two: Domination and characterization"

Copied!
14
0
0

Loading.... (view fulltext now)

Full text

(1)

Contents lists available atScienceDirect

Discrete Applied Mathematics

journal homepage:www.elsevier.com/locate/dam

Triangle-free projective-planar graphs with diameter two:

Domination and characterization

Dibyayan Chakraborty

a

, Sandip Das

b

, Srijit Mukherjee

b

, Uma kant Sahoo

b

, Sagnik Sen

c,

aIndian Institute of Science, Bengaluru, India

bIndian Statistical Institute, Kolkata, India

cIndian Institute of Technology Dharwad, India

a r t i c l e i n f o

Article history:

Received 4 February 2020

Received in revised form 8 December 2022 Accepted 3 January 2023

Available online xxxx Keywords:

Projective-planar

Forbidden minor characterization Domination number

a b s t r a c t

In 1975, Plesník characterized all triangle-free planar graphs as having a diameter 2. We characterize all triangle-free projective-planar graphs having a diameter 2 and discuss some applications. In particular, the main result is applied to calculate the analogue of clique numbers for graphs, namely, colored mixed graphs, having different types of arcs and edges.

©2023 Elsevier B.V. All rights reserved.

1. Introduction and main results

In 1975, Plesník [19] characterized all triangle-free planar graphs1having diameter 2 by proving the following result.

Theorem 1(Plesník 1975 [19]).A triangle-free planar graph G has a diameter2if and only if it is isomorphic to one of the following graphs:

(i) K1,nfor n

2, (ii) K2,nfor n

2,

(iii) the graph C5(m

,

n)obtained by adding(m

+

n)degree-2vertices to the5-cycle C5

= v

1

v

2

v

3

v

4

v

5

v

1, for m

,

n

0, in such a way that m of the vertices are adjacent to

v

1

, v

3and n of the vertices are adjacent to

v

1

, v

4.

We prove the analogue of Plesník’s result for projective-planar graphs, that is, graphs that can be embedded on the non-orientable surface of Euler genus one (also known as the real projective plane) without their edges crossing each other except, maybe, on the vertices. For convenience, let us refer to the graphs listed inTheorem 1asPlesník graphs.

Theorem 2. A triangle-free projective-planar graph G has diameter2if and only if it is isomorphic to one of the following:

(i) a Plesník graph, (ii) K3,3or K3,4,

This work is partially supported by the IFCAM project Applications of graph homomorphisms (MA/IFCAM/18/39).

Corresponding author.

E-mail address: sen007isi@gmail.com(S. Sen).

1 In this article, we use the notation and terminology of ‘‘Introduction to Graph Theory’’ by D. B. West [22].

https://doi.org/10.1016/j.dam.2023.01.001 0166-218X/©2023 Elsevier B.V. All rights reserved.

(2)

Fig. 1.(i) The Petersen graphP10, (ii) The Wagner graphW8, (iii) The graphW8+, (iv) The Grötzsch graphM11, (v) The graphM11, (vi) The graph M11=, (vii) The graphK3,4.

(iii) the graph K3,3(n)obtained by adding(n

1)parallel edges e2

,

e3

, . . . ,

ento one of the edges e1of K3,3and subdividing each ei exactly once for n

1,

(iv) the graph K3,4(n)obtained by adding(n

1)parallel edges e2

,

e3

, . . . ,

ento one of the edges e1of K3,4and subdividing each ei exactly once for n

1,

(v) one of the seven graphs depicted inFig.1.

Let us now discuss a few more results regarding properties of graphs having small diameters that can be embedded on a given surfaceSto place our work into context. SinceShas an Euler characteristic, it follows from the Euler’s formula [16]

that any graph embedded inShas a bounded minimum degree. This implies that if we consider such a graph with diameter 2, then its domination number is at most its minimum degree.

In 1996, MacGillivray and Seyffarth [14] proved that planar graphs with diameter 2 have domination numbers at most 3. In 2002, Goddard and Henning [9] showed that there is exactly one planar graph having diameter 2 that has a domination number equal to 3. They also proved that for each surface (orientable or non-orientable)S, there are finitely many graphs having diameter 2 and domination number at least 3 that can be embedded inS. A natural question to ask in this context is the following.

Question 1. Given a surfaceS, can you find the list of all graphs having diameter2and domination number at least3that can be embedded onS?

As we just mentioned, Goddard and Henning [9] answered Question 1when S is the sphere (or equivalently, the Euclidean plane). However, it seems that the question can be very difficult to answer in general as the tight upper bounds on the domination number for a family of graphs that can be embedded on a surface, other than the sphere, is yet to be found. Therefore, it makes sense to ask the following natural restriction instead.

Question 2. Given a surfaceS, can you find the list of all triangle-free graphs having a diameter2and domination number at least3that can be embedded onS?

Notice that, Plesník’s characterization implies that the answer forQuestion 2is the empty list whenSis the sphere.

On the other hand, the following immediate corollary ofTheorem 2answers the question whenSis the projective plane, along with implying that the domination number of triangle-free projective-planar graphs having diameter 2 is at most three (following our earlier discussions on Euler’s characteristic). Note that the domination number of graphs shown in Fig. 1is three.

Theorem 3. Let G be a triangle-free projective-planar graph having a diameter2. Then (a) The domination number

γ

(G)of G is at most3.

(b) If

γ

(G)

=

3, then G is isomorphic to one of the seven graphs depicted inFig.1.

AsTheorem 3follows directly from Theorem 2, we will focus on proving Theorem 2. This is done in Section2. In Section3, we provide some direct implications of our results in determining the absolute clique number of the families of triangle-free projective-planar graphs, which is an important parameter in the theory of homomorphisms of colored mixed graphs.2

2. Proof ofTheorem 2

It is known, due to Euler’s formula [16] for projective-planar graphs, that any triangle-free projective-planar graphG has minimum degree

δ

(G)

3. Therefore, any triangle-free projective-planar graph having a diameter 2 has a domination number at most 3.

Notice that as the family of projective-planar graphs is minor-closed, due to The Graph Minor Theorem [20], there exists a finite setSof graphs such that a graphGis projective-planar if and only ifGdoes not contain a minor fromS. Actually, an explicit description of the setSis provided in [2] (see [16]) and it contains 35 graphs. However, we will not need the full list for our proof — to be precise, we will use only three graphs from that list: (1)K3,5, (2)K4,4, i.e., the graph obtained fromK4,4by deleting exactly one edge, and (3) the graphF0depicted inFig. 2.

2 The related definitions are deferred to Section3.

12

(3)

Fig. 2. The graphs (a)F0, (b)F1, (c)F2, and (d)F3form the graph familyD.

Observation 1([2]; see [16]).The graphs K3,5, K4,4, and F0are not projective-planar.

Thus any graph containing K3,5,K4,4, or F0 as a minor is not projective-planar as well. Even though the previous statement is obvious, we will present it as another observation as it will be frequently used in our proofs.

Observation 2([2]; see [16]).If G contains K3,5, K4,4, or F0as a minor, then G is not a projective-planar graph.

Now we get into the more technical part of our proof. First of all, for convenience, let us denote the family of all triangle-free projective-planar graphs having diameter 2 byPP2. Therefore, what we are trying to do here is to provide a list of all graphs inPP2. We already know that ifG

PP2, then its minimum degree

δ

(G) is at most 3. We will use this as the basis of our case analysis. Observe that anyG

PP2is connected. Therefore, the logical first step is to handle the graphs having a degree one vertex.

2.1. Characterizing graphs inPP2having minimum degree at most2

Lemma 1. If

δ

(G)

=

1for a graph G

PP2, then G is isomorphic to K1,nfor some n

2.

Proof. Let

v

be a degree-1 vertex inGhaving

v

1as its only neighbor. AsGhas diameter 2,

v

1must be adjacent to all the vertices inV(G)

\ { v, v

1

}

. Moreover, asGis triangle-free, the set of all neighborsN(

v

1) of

v

1is an independent set. □

The next natural step is to consider the graphs having minimum degree equal to 2.

Lemma 2. If

δ

(G)

=

2for a graph G

PP2, then G is isomorphic to K2,n+2, C5(m

,

n), K3,4(n), or K3,3(n)for some m

,

n

0.

Proof. Let

v

be a degree-2 vertex havingN(

v

)

= { v

1

, v

2

}

. Let C

=

(N(

v

1)

N(

v

2))

\ { v }

andSi

=

N(

v

i)

\

(C

∪ { v }

) fori

∈ {

1

,

2

}

.

S1

S2induces a complete bipartite graph (else the end vertices of any non-edge would be at a distance greater than 2, a contradiction) and as

δ

(G)

2, both sets are nonempty.

If

|

S1

| ≥ |

S2

| ≥

3, then we find aK4,4by taking the graph induced byS1

S2

∪ { v

1

, v

2

}

. This is a contradiction due to Observation 2. Thus we must have

|

S2

| ≤

2.

If

|

S2

| =

2, then

|

S1

| ≤

3 as otherwise we can contract the edge

vv

1to find aK3,5induced byS1

S2

∪ { v

1

, v

2

}

. This is a contradiction due toObservation 2.

Now observe that

|

S1

| =

3 and

|

S2

| =

2 impliesGis isomorphic toK3,4(n), wheren

= |

C

| +

1. Similarly,

|

S1

| =

2 and

|

S2

| =

2 impliesGis isomorphic toK3,3(n), wheren

= |

C

| +

1.

If

|

S2

| =

1,

|

S1

|

can have any value greater than or equal to 1. In this case,Gis isomorphic toC5(m

,

n), wherem

= |

C

|

andn

= |

S1

| −

1. □

2.2. Characterizing graphs inPP2that are3-regular

This leaves us with the final case: considering the graphs having minimum degree equal to 3. We break this case into two parts, namely, whenGis 3-regular and whenGis not 3-regular, and tackle them separately. Also we will use some new terminologies.

A vertex u reachesa vertex

v

if they are adjacent or they have a common neighbor. In particular, if

w

is a common neighbor ofuand

v

, then we use the termureaches

v

via

w

.

Lemma 3. If a3-regular graph G

PP2, then G is isomorphic to either K3,3or W8or P10.

13

(4)

Proof. Let

v ∈

V(G) be any vertex having neighbors

{ v

1

, v

2

, v

3

}

. Moreover, letSidenote the set of vertices inG

\ { v }

which are adjacent to exactlyivertices among

{ v

1

, v

2

, v

3

}

. Note that, asGhas diameter 2, every vertex inG

\{ v, v

1

, v

2

, v

3

}

belongs to exactly one ofS1

,

S2, andS3.

Observe that asGis 3-regular, we must have

|

S3

| ≤

2. Moreover, if

|

S3

| =

2, thenGis isomorphic toK3,3.

If

|

S3

| =

1, then note that we must have

|

S2

| ≤

1 as otherwise, it will force one of the vertices among

{ v

1

, v

2

, v

3

}

to have at least two neighbors inS2, and hence have at least four neighbors inG, contradicting the 3-regularity ofG.

Furthermore, if

|

S3

| = |

S2

| =

1, then without loss of generality we may assume thatS2

= {

u

} ⊆

N(

v

1)

N(

v

2). Thus umust reach

v

3via some vertexu

S1

N(

v

3). Now each vertex among

{ v

1

, v

2

, v

3

}

already has three neighbors and thus there cannot be any other vertex inG. Also all vertices exceptuhave degree 3 at present. Thus the 3-regularity of Gforces us to include a new vertex adjacent touin the graph, a contradiction. Therefore,Gcannot have

|

S3

| = |

S2

| =

1.

Thus if

|

S3

| =

1, then we must haveS2

= ∅

. However, due to the 3-regularity ofG, each vertex among

{ v

1

, v

2

, v

3

}

has exactly one neighbor inS1. Let us assume that the neighbors of

v

1

, v

2, and

v

3inS1are

w

1

, w

2, and

w

3, respectively. Now, as each vertex among

{ v

1

, v

2

, v

3

}

already has three neighbors, there cannot be any other vertex inG. In fact, each vertex ofGother than

w

1

, w

2, and

w

3has degree 3 already. Thus

w

1

, w

2, and

w

3must reach all of

v

1

, v

2, and

v

3either directly or via themselves. That forces

w

1

, w

2, and

w

3to create a triangle, contradicting the triangle-free property ofG. Therefore, Gcannot have

|

S3

| =

1.

Now let us consider the situation where

|

S3

| =

0. First observe that

|

S2

| ≤

3 in this case, as otherwise one vertex among

{ v

1

, v

2

, v

3

}

has degree at least 4.

If

|

S2

| =

3, then without loss of generality, we may assume thatS2

= {

u1

,

u2

,

u3

}

whereui

S2

\

N(

v

i) for alli

∈ {

1

,

2

,

3

}

. Now, as every vertex among

{ v

1

, v

2

, v

3

}

already has three neighbors each, there cannot be any other vertex inG. Hence S1

= ∅

. Thus, in particular, the vertexu1must reach

v

1via some vertex ofS2. That will create a triangle, a contradiction.

So

|

S2

| ≤

2.

If

|

S2

| =

2 withS2

= {

u1

,

u2

}

, then without loss of generality, assume that

v

3 is a common neighbor ofu1 andu2. Moreover, the sum of the degrees of

v

1

, v

2, and

v

3 at the moment is 7 and therefore we must have exactly two more vertices inG. Thus,

|

S1

| =

2 and we may assume thatS1

= { w

1

, w

2

}

. Observe thatu1 and u2 must have exactly one neighbor each inS1as they cannot be adjacent to each other in order to avoid creating a triangle. This implies that there are exactly two edges between the setsS1andS2. Thus at least one vertex ofS1does not have degree 3 unless

w

1and

w

2

are adjacents. Hence

w

1and

w

2must be adjacent. This implies that

w

1and

w

2do not have a common neighbor. Therefore, without loss of generality, we may assume that

w

i andui are adjacent to

v

i for alli

∈ {

1

,

2

}

. Hence the edgesu1

w

2and u2

w

1are inG. Observe thatGis isomorphic toW8in this case.

We have a total of nine vertices, not possible for a 3-regular graph (as nine is an odd number).

If

|

S2

| =

0, then each

v

ihas exactly two neighbors

w

i and

w

i inS1for alli

∈ {

1

,

2

,

3

}

. Without loss of generality,

w

1

reaches

v

2and

v

3via

w

2and

w

3, respectively. As

w

1already has three neighbors,

w

2and

w

3must reach

v

1via

w

1. Note that,

w

2cannot reach

v

3via

w

3in order to avoid a triangle. Therefore,

w

2reaches

v

3via

w

3. Similarly,

w

3reaches

v

2via

w

2. This implies thatGis isomorphic toP10.

2.3. Characterizing not regular graphs inPP2having minimum degree3

Finally, the case where

δ

(G)

=

3 and∆(G)

4 is handled. The proof ofLemma 4is lengthy; in order to make the proof easier to follow, we have divided it into several claims and lemmas and presented it in a separate subsection.

Lemma 4. If

δ

(G)

=

3and(G)

4for a graph G

PP2, then G is isomorphic to K3,4, K3+,4, W8+, M11, M11, or M11=. We will begin by presenting some basic conventions to be used throughout this section.

2.3.1. Conventions used in the proof ofLemma4

Let

v ∈

V(G) be a vertex with maximum degree and letN(

v

)

= { v

1

, v

2

, v

3

, v

4

} ∪

Xwhere Xmay or may not be

. Moreover, letSi denote the set of vertices inG

\ { v }

which are adjacent to exactlyivertices among

{ v

1

, v

2

, v

3

, v

4

}

(see Fig. 3). Furthermore, letm2be the cardinality of a maximum matching inS2.

2.3.2. Basic structural properties

The proof ofLemma 4runs via a series of claims and lemmas. In the case of the claims, we always assume that

δ

(G)

=

3 andd(

v

)

=

(G)

4 for a graphG

PP2.

This brings us to our first two observations.

Claim 1. A vertex in S3

S4is not adjacent to a vertex in S2

S3

S4.

Proof. Any vertex inS4

S3has at least one neighbor in common with any vertex inS2

S3

S4. Hence, any edge between S4

S3andS2

S3

S4will create a triangle.

Claim 2. The value of

|

S4

| + |

S3

| +

m2is at most2.

14

(5)

Fig. 3. Illustrations of our convention.

Proof. Observe that each vertex ofS3reaches three of the four vertices among

{ v

1

, v

2

, v

3

, v

4

}

directly and one of them via a vertex ofS1(byClaim 1). Therefore, if we contract all the edges between

{ v

1

, v

2

, v

3

, v

4

}

andS1, then each vertex of S3becomes adjacent to every vertex of

{ v

1

, v

2

, v

3

, v

4

}

. Moreover, suppose there is an edge having both its end vertices inS2, then these end vertices cannot have a common neighbor, else a triangle is induced. Contracting this edge, the new resulting vertex will correspond to a vertex adjacent to each of

{ v

1

, v

2

, v

3

, v

4

}

. Therefore, if

|

S4

| + |

S3

| +

m2

3, thenG will contain aK4,4-minor. □

Therefore, in particular, the above claim implies that

|

S4

| + |

S3

| ≤

2. This bound will be the basis of our case study.

2.3.3. Case:

|

S4

| + |

S3

| =

2

Claim 3. If

|

S4

| + |

S3

| =

2, then S2

= ∅

.

Proof. Recall that each vertex ofS3reaches three of the four vertices among

{ v

1

, v

2

, v

3

, v

4

}

directly and one of them via a vertex ofS1(byClaim 1). If

|

S4

| + |

S3

| =

2, thenm2

=

0 (byClaim 2). Now ifS2

̸= ∅

, then each vertex ofS2reaches two of the four vertices among

{ v

1

, v

2

, v

3

, v

4

}

directly and two of them via vertices ofS1. This is implied byClaim 1and the following: any vertex inS2cannot reach the two non-adjacent vertices in

{ v

1

, v

2

, v

3

, v

4

}

via a vertex inS2(asm2

=

0).

Hence, contract all edges betweenS1and

{ v

1

, v

2

, v

3

, v

4

}

to obtain aK4,4, a contradiction. □

Claim 4. If S4

S3

= {

u1

,

u2

}

and

v

i is a common neighbor of u1and u2for some i

∈ {

1

,

2

,

3

,

4

}

, then no vertex

w ∈

S1is adjacent to

v

i.

Proof. By Claim 3, we know that S2

= ∅

. Therefore, each vertex in S4

S3 would reach non-adjacent vertices in

{ v

1

, v

2

, v

3

, v

4

}

via some vertices inS1. If there exists a vertex

w ∈

S1

N(

v

i), where

v

iis as defined in the lemma statement, then

w

cannot be adjacent to any of

{

u1

,

u2

}

(else a triangle is induced). SinceS2

= ∅

(byClaim 3), the vertex

w

reaches vertices in

{ v

1

, v

2

, v

3

, v

4

} \ { v

i

}

via vertices inS1. Contract all the edges betweenS1and

{ v

1

, v

2

, v

3

, v

4

}

except

wv

ito obtain aK4,4, a contradiction. □

Claim 5. If

|

S4

| + |

S3

| =

2, then X

= ∅

.

Proof. Assume thatS4

S3

= {

u1

,

u2

}

and there exists anx

X.

If

|

S4

| =

2, thenxreachesu1andu2directly or via some other vertices not adjacent to

{ v

1

, v

2

, v

3

, v

4

}

(else a triangle is induced). Contract the edges betweenxand those vertices (if they exist) via whichxreachesu1

,

u2to obtain aK3,5, a contradiction.

If

|

S4

| =

1 and without loss of generalityu1

S4andu2

S3, thenxreachesu1directly or via some other vertex

w

1

not adjacent to

{ v

1

, v

2

, v

3

, v

4

}

(else a triangle is induced). Contract the edgex

w

1if it exists. Observe thatu2is adjacent to some vertex

w

2

S1in order to reach all of

{ v

1

, v

2

, v

3

, v

4

}

. Contractu2

w

2. Note thatxreachesu2directly, or via

w

2or via some other vertex

w

3which is not adjacent to

{ v

1

, v

2

, v

3

, v

4

}

. Contractx

w

3, if it exists, to obtain aK3,5, a contradiction.

If

|

S4

| =

0 and thusu1

,

u2

S3, thenu1andu2may be non-adjacent to the same or different vertices in

{ v

1

, v

2

, v

3

, v

4

}

. Case 1. If they are non-adjacent to different vertices of

{ v

1

, v

2

, v

3

, v

4

}

, then without loss of generality assume thatui is not adjacent to

v

i fori

∈ {

1

,

2

}

. In this case,uimust reach

v

ivia some

w

i

S1(byClaim 1) andxmust reachui directly or via

w

i or via some

w

i

S1with

w

i

̸∈ { w

1

, w

2

}

. Contract the edgesui

w

i andx

w

i (if they exist) for all i

∈ {

1

,

2

}

to obtain aK3,5, a contradiction.

Case 2. If they are non-adjacent to the same vertex, without loss of generality say,

v

4 of

{ v

1

, v

2

, v

3

, v

4

}

, then

v

4 must have at least two neighbors

w

1

, w

2as the degree of

v

4 is at least three. Also

w

1

, w

2

S1 (byClaim 1). Due to Claims 3and4, we know that the only way for

w

ito reach

v

1is viau1oru2. Moreover, for eachi

∈ {

1

,

2

}

,uimust reach

v

4 via some vertex ofS1(byClaim 1). Therefore, we must have a perfect matching between

{

u1

,

u2

}

and

{ w

1

, w

2

}

. Without loss of generality, assume that perfect matching be

{

u1

w

1

,

u2

w

2

}

. Furthermore, observe that if xis adjacent to any one ofu1oru2, we can rename the vertices ofN(

v

) to reduce this to a case where

|

S4

| ≥

1, which we have already handled earlier in the proof of this lemma. Therefore,xmust reachuivia

w

i or via some

15

(6)

vertex

w

i

̸∈ {

u1

,

u2

, w

1

, w

2

}

for alli

∈ {

1

,

2

}

. Contract the edgesui

w

i andx

w

i (if they exist) for alli

∈ {

1

,

2

}

to obtain aK3,5, a contradiction.

This concludes the proof. □

Now that we have shown the setX

= ∅

when

|

S4

| + |

S3

| =

2, we can try to characterize the graphs for this case.

Lemma 5. If

δ

(G)

=

3and d(

v

)

=

(G)

4for a graph G

PP2, then the following holds: if

|

S4

| =

2, then G is isomorphic to K3,4.

Proof. If

|

S4

| =

2, then X

=

S3

=

S2

=

S1

= ∅

due to Claims 2–5. The only vertices in the graphs other than

{ v, v

1

, v

2

, v

3

, v

4

}

are the two vertices inS4. ThusGis isomorphic toK3,4.

Claim 6. It is not possible to have

|

S4

| = |

S3

| =

1.

Proof. If

|

S4

| = |

S3

| =

1, then without loss of generality assume thatu1

S4,u2

S3

\

N(

v

4). Observe thatX

=

S3

=

S2

= ∅

due toClaims 2,3and5. Moreover, all the vertices inS1are adjacent to

v

4due toClaim 4. Asu2must reach

v

4via some vertex ofS1, the setS1is not empty. However, any vertex ofS1has exactly two neighbors, namely

v

4andu2, contradicting

δ

(G)

=

3. □

Lemma 6. If

δ

(G)

=

3and d(

v

)

=

(G)

4for a graph G

PP2, then the following holds: if

|

S3

| =

2, then G is isomorphic to W8+.

Proof. Assume thatS3

= {

u1

,

u2

}

. ThusX

=

S4

=

S2

= ∅

due toClaims 2,3and5. Observe that it is enough to consider the following two cases: (i)u1andu2are both non-adjacent to

v

4, and (ii)uiis non-adjacent to

v

i fori

∈ {

1

,

2

}

.

Case (i). Ifu1andu2are both non-adjacent to

v

4, then all the vertices inS1are adjacent to

v

4due toClaim 4. The vertices

v, v

1

, v

2

, v

3

, v

4

,

u1, andu2and the vertices belonging toS1are all of the vertices ofG. As

δ

(G)

=

3, each vertex ofS1must be adjacent to bothu1andu2. Furthermore,S1must have at least two vertices, say

w

1and

w

2, as

δ

(G)

=

3. Now contract

vv

4to obtain aK3,5induced by

{

u1

,

u2

,

(

vv

4)

} ⊔ { v

1

, v

2

, v

3

, w

1

, w

2

}

where (

vv

4) denotes the new vertex obtained by contracting the edge

vv

4. Thus this case is not possible sinceK3,5is not projective planar.

Case (ii). Ifuiis non-adjacent to

v

ifori

∈ {

1

,

2

}

, then all the vertices inS1are adjacent to either

v

1or

v

2due toClaim 4.

Therefore, the vertices

v, v

1

, v

2

, v

3

, v

4

,

u1, andu2 and the vertices belonging to S1 are all of the vertices of G. Suppose thatS1

= { w

1

, w

2

, . . . , w

k

, w

1

, w

2

, . . . , w

r

}

where

w

is are adjacent to

v

1and

w

js are adjacent to

v

2 where (i

,

j)

∈ {

1

,

2

, . . . ,

k

} × {

1

,

2

, . . . ,

r

}

. Each

w

i reaches

v

3viau1and each

w

jis reaches

v

3 viau2 for all (i

,

j)

∈ {

1

,

2

, . . . ,

k

} × {

1

,

2

, . . . ,

r

}

. Furthermore as

δ

(G)

=

3, each

w

i must be adjacent to some

w

jand each

w

p must be adjacent to some

w

q. Without loss of generality and due to symmetry, we may assume that 1

r

k. Ifk

2, then contract the edges u2

w

j for allj

∈ {

1

,

2

, . . . ,

r

}

to obtain the new vertex (u2

w

j), and contract the edge

vv

1to obtain the new vertex (

vv

1). Observe that, in this contracted graph, the vertices

{

u1

,

(

vv

1)

,

(u2

w

j)

} ⊔ { w

1

, w

2

, v

2

, v

3

, v

4

}

induce aK3,5subgraph, a contradiction. Therefore,k

=

r

=

1. ThusGis isomorphic toW8+.

This ends the proof of the lemma. □

This concludes the case when we have

|

S4

| + |

S3

| =

2. We will present the summary of it in the following lemma.

Lemma 7. If

δ

(G)

=

3and d(

v

)

=

(G)

4for a graph G

PP2, then the following holds: if

|

S4

| + |

S3

| =

2, then G is isomorphic to K3,4or W8+.

Proof. Follows directly fromLemma 5,Claim 6, andLemma 6. □

It remains to analyze the situations when

|

S4

| + |

S3

| ≤

1. The first case is when

|

S4

| + |

S3

| =

1.

2.3.4. Case:

|

S4

| + |

S3

| =

1

Claim 7. If

|

S4

| + |

S3

| =

1, then S2

̸= ∅

.

Proof. Let us assume the contrary and suppose thatS2

= ∅

. Furthermore, assume thatS4

S3

= {

u1

}

and thatu1 is adjacent to

{ v

1

, v

2

, v

3

}

. First we will show that it is not possible for any

v

i, fori

∈ {

1

,

2

,

3

}

, to have two neighbors inS1.

Hence without loss of generality assume that

v

1is adjacent to

w

1

, w

2

S1. Observe that both

w

1and

w

2must reach

v

2

, v

3, and

v

4via some vertices fromS1

\ { w

1

, w

2

}

andu1 must reach

v

4 via some vertex fromS1

\ { w

1

, w

2

}

(all due to

16

(7)

Claim 1). Now contract all the edges between

{ v

2

, v

3

, v

4

}

andS1

\ { w

1

, w

2

}

to obtain aK4,4-minor, a contradiction. Thus each

v

is, fori

∈ {

1

,

2

,

3

}

, can have at most one neighbor inS1.

However,

δ

(G)

=

3 implies that each

v

imust be adjacent to exactly one vertex (say)

w

i fromS1fori

∈ {

1

,

2

,

3

}

. Now note that

w

1must reach

v

2and

v

3via

w

2and

w

3, respectively and

w

2must reach

v

3via

w

3. This creates a triangle induced by

{ w

1

, w

2

, w

3

}

inG, a contradiction.

Claim 8. If

|

S4

| =

1and

|

S3

| =

0, then X

= ∅

.

Proof. LetS4

= {

u1

}

and letx

X.Claim 7implies the existence of a vertex

w

1

S2. Without loss of generality assume that

w

1is adjacent to

v

1and

v

2.

Note thatxreachesu1directly or via some vertexa(say) not adjacent to any of

{ v

1

, v

2

, v

3

, v

4

}

in order to avoid creating a triangle inG. Moreover,

w

1reachesx

, v

3, and

v

4via some vertices not adjacent to any of

{ v

1

, v

2

}

. LetAdenote the set of vertices via which

w

1reachesx

, v

3, and

v

4. Contract the edges betweenA

\ {

a

}

and

w

1and the edgexa. The vertices

{ v, w

1

,

u1

} ⊔ {

x

, v

1

, v

2

, v

3

, v

4

}

form the partition of aK3,5-minor, a contradiction.

Claim 9. If

|

S4

| =

1and

|

S3

| =

0, then m2

=

1.

Proof. ByClaim 2,m2

1. Next, suppose thatS4

= {

u1

}

andm2

=

0. That means every vertex ofS2(which is non-empty byClaim 7) must reach its non-adjacent

v

is via vertices ofS1 (byClaim 1 and m2

=

0). Therefore, if

|

S2

| ≥

2, then contracting the edges betweenS1and

{ v

1

, v

2

, v

3

, v

4

}

will create aK4,4-minor.

Thus, we have

|

S2

| =

1. Without loss of generality assume thatS2

= { w }

and that

w

is adjacent to

v

1and

v

2. Notice that

w

must reach

v

3and

v

4via

w

3

, w

4

S1, respectively (byClaim 1andm2

=

0). Thus to avoid creating a triangle,

w

3must reach

v

4via

w

4

S1. Moreover, to avoid creating a triangle,

w

4 must reach

v

1via some

w

1

S1.

Notice that,

w

1 reaches

v

2

, v

3, and

v

4 via some elements ofS1. Thus, if we contract all the edges betweenS1 and

{ v

2

, v

3

, v

4

}

, we will create aK4,4-minor.

Therefore,m2

1. Sincem2

1 byClaim 2, we havem2

=

1. □

Lemma 8. If

δ

(G)

=

3and(G)

4for a graph G

PP2, then the following holds: if

|

S4

| =

1and

|

S3

| =

0, then G is isomorphic to K3,4.

Proof. LetS4

= {

u1

}

and, thus, byClaim 9we know thatm2

=

1. Then without loss of generality we may assume the existence of an edge

w

1

w

2such that

w

1

, w

2

S2,

w

1is adjacent to

v

1 and

v

2, and

w

2is adjacent to

v

3 and

v

4. If there are no other vertex or edge inG, thenGis isomorphic toK3,4.

However, if there is another vertex

w

3

S2and if

w

3reaches

{ v

1

, v

2

, v

3

, v

4

}

directly or via some vertices except

w

1

and

w

2, then contract the edge

w

1

w

2. Also contract the edges between

w

3and the vertices via which

w

3reaches

v

is, for i

∈ {

1

,

2

,

3

,

4

}

. This will result in aK4,4-minor.

On the other hand, if there is a

w

3

S2 and if

w

3 reaches

{ v

1

, v

2

, v

3

, v

4

}

directly or via

w

i for somei

∈ {

1

,

2

}

, then Gis the graphF1 (depicted inFig. 2(b)) that contains the graphF0 (depicted inFig. 2(a)) as a subgraph, and thus as a minor. □

So far we were dealing with the case when Gis a graph with

|

S4

| =

1 and

|

S3

| =

0. Now we turn our attention towards the case whenG is a graph with

|

S4

| =

0 and

|

S3

| =

1. Initially, we will observe some properties that this condition implies. However, finally, the satisfaction of those properties will turn out to be impossible, thereby proving that there are no required graphs with

|

S4

| =

0 and

|

S3

| =

1.

Claim 10. If

|

S4

| =

0and

|

S3

| =

1, then X

= ∅

.

Proof. Suppose that X

̸= ∅

andx

X. LetS3

= {

u1

}

and without loss of generality letu1 be adjacent to

v

1

, v

2

, v

3. Therefore,u1must reach

v

4via

w

4

S1(byClaim 1). We know thatS2

̸= ∅

due toClaim 7. Also letu2

S2.

Ifu2reaches

v

4directly or via any vertex other than

w

4, then contract the edgeu1

w

4, all the edges connectingu2to its neighbors via whichu2reaches

v

1

, v

2

, v

3or

v

4, and all the edges connectingxto its neighbors via whichxreachesu1 andu2, in order to obtain aK3,5-minor (see the vertices in the partition

{ v,

u1

,

u2

} ⊔ {

x

, v

1

, v

2

, v

3

, v

4

}

).

Thus u2reaches

v

4via

w

4 and nothing else. Hence without loss of generality, we may assume thatu2is adjacent to

v

1 and

v

2 and thatu2reaches

v

3 via

w

3

S1(if

w

3

S2, then

w

3must be adjacent to

v

3

, v

4and by similar arguments as the previous case existenceK3,5 minor can be shown). Moreover, as

δ

(G)

=

3, there must be a

w

4

S1 adjacent to

v

4. On the other hand,

v

1 cannot have a neighbor inS1, as otherwise we may contract all the edges betweenS1 and

{ v

2

, v

3

, v

4

}

to obtain aK4,4-minor. Therefore,

w

4 must reach

v

1 via u1 (if

w

4 reaches

v

1 viau2, then a K3,5-minor is formed: see the vertices in the partition

{ v,

u1

,

u2

} ⊔ {

x

, v

1

, v

2

, v

3

, v

4

}

). Now contract the edgesu1

w

4

,

u2

w

3

,

u2

w

4, and all the edges connectingx to its neighbors via which x reaches u1

,

u2. Ifx is adjacent to

w

4, then also contract the edge connectingxto its neighbor via whichx reaches

w

4. This creates aK3,5-minor (see the vertices in the partition

{ v,

u1

,

u2

} ⊔ {

x

, v

1

, v

2

, v

3

, v

4

}

).

17

References

Related documents

Harmonization of requirements of national legislation on international road transport, including requirements for vehicles and road infrastructure ..... Promoting the implementation

Since planar graphs have 3 dimensional box represen- tations computable in polynomial time [20], using our algorithm of Theorem 1, we get an FPT algorithm for boxicity, giving a 2

A cograph G is clique vertex irreducible if and only if it can be reduced to a trivial graph by recursively deleting vertices of full degree in each of the

The cliques of ∆(G) are induced by the vertices corresponding to the edges of G incident on a vertex of degree at least 3 whose other end vertices induce a complete graph and by

The petitioner also seeks for a direction to the opposite parties to provide for the complete workable portal free from errors and glitches so as to enable

The value of a multicut is at least the value of the sum-multicommodity flow, and the ratio of the minimum multicut to the maximum (integral/half-integral) sum multicommodity flow

Two non-isomorphic graphs with identical spectrum are called cospectral and two non-cospectral graphs with the same energy are called equienergetic.. The energies of some

This is to certify that the thesis entitled ‘Studies on some generalizations of line graph and the power domination problem in graphs’ submitted to the Cochin University of Sci-