Some network topological notions of the Mycielskian of a graph

Peer review under responsibility of Kalasalingam University.

Abstract

Efficiency and reliability are two important criteria in the designing of a good interconnection network. Network topological notions such as wide diameter, fault diameter, diameter vulnerability and -domination can be used to study the efficiency and reliability of a network. In this paper we study these notions in the Mycielskian of a graph and its iterates.

Keywords:

• Mycielskian
• Wide diameter
• Diameter vulnerability
• Fault diameter
• -domination

1 Introduction

An interconnection network connects the processors of a parallel and distributed system. The topological structure of an interconnection network can be modeled by a connected graph where the vertices represent components of the network and the edges represent communication links between them. Some graph theoretic techniques that are used to study the efficiency and reliability of a network are discussed in [1,2].

Let be a simple graph with vertex set and edge set . The degree of a vertex in , is the number of edges incident with in . The minimum degree and the maximum degree in a graph are denoted by and respectively. The neighborhood of , written , is the set and is called a neighbor of if . The subgraph of induced by is denoted by .

The distance between and in a connected graph , , is the length of a shortest path joining and in . The diameter of a graph , diam(G), is the maximum distance between any two vertices in . The diameter is often taken as a measure of efficiency, especially for networks with maximum time-delay or signal degradation.

The vertex connectivity, of a connected graph is the minimum number of vertices whose removal from results in a disconnected graph or . The edge connectivity of a connected graph , is the minimum number of edges whose removal makes the graph disconnected. A connected graph is said to be -connected if and -edge connected if . The connectivity is used to measure network fault tolerance capacity.

For every integer , , a -container between any two distinct vertices and of is a collection of ‘’ internally vertex disjoint paths between them. Let denote a -container between and . In , the parameter is the width of the container. The length of the container is the length of a longest path among all paths in . The -wide distance between and is the minimum , over all -containers between and . The -wide diameter of , is the maximum of among all pairs of vertices in , . is called the wide diameter of [1]. A small wide diameter is preferred, since it enables fast multi-path communication. The wide diameter of some networks is studied in [3,4].

Fault diameter estimates the impact on the diameter of a graph, when the deletion of vertices occur. The vertex fault diameter denoted by is defined as [5].

Vulnerability [6,7] is a measure of the ability of the system to withstand vertex or edge faults and maximum routing delay. The maximum diameter of a graph obtained by deleting edges from a -edge connected graph with diameter is denoted by and is used to study the diameter vulnerability of graphs by edge deletion.

Let be a -connected graph (), , and . A path from to some vertex in is called a -path. A set of internally disjoint -paths is called a -container, denoted by . The length of a longest path among all paths in is called the length of . For a given integer , if there exists a -container with length at most , then we say that can -dominate . is called an -dominating set of , if it -dominates every vertex in . The set of all -dominating sets in is denoted by . The parameter is called the -dominating number of and an -dominating set of is called minimum if [2]. This parameter is used to characterize the reliability of resources-sharing in a network and has been recently studied in [8].

In a search for triangle-free graphs with arbitrarily large chromatic number, Mycielski developed an interesting graph transformation known as the Mycielskian of a graph [9]. For a graph , the Mycielskian of is the graph with the vertex set , where and the edge set . The vertex is called the twin of the vertex and vice versa. The vertex is called the root of . For , is defined iteratively by setting .

In [10], Fisher et al. studied the Hamiltonicity and diameter of the Mycielskian and proved that if is hamiltonian, then so is and diameter of . Balakrishnan and Francis Raj determined the vertex connectivity and edge connectivity of Mycielskian in [11]. Recently in [12], Guo et al. showed that for a connected graph with , is super connected if and only if and is super edge connected if and only if . These results motivated the study of network topological properties of the Mycielskian of a graph.

In this paper, we study the wide diameter, the fault diameter, the diameter vulnerability and the -domination of the Mycielskian of a graph. It is interesting to observe that the Mycielskian and its iterates produce large networks and preserve some nice properties of networks such as fast multi-path communication, high fault tolerance and reliable resource sharing.

The following results [11] are used in this paper.

Lemma 1.1

For a connected graph , if and only if .

Lemma 1.2

If is a connected graph, then if and only if for each i, .

Lemma 1.3

If is a connected graph, then if and only if and .

Lemma 1.4

If is a connected graph, then .

All graphs considered in this paper are simple, finite and undirected. For all notions not given here, see [9].

2 Wide diameter of the Mycielskian of a graph

To determine the wide diameter of the Mycielskian of a graph, we first study the containers in the Mycielskian.

2.1 Containers in the Mycielskian of a graph

In the following five propositions, is a connected graph with . Then by Lemma 1.1, .

Proposition 2.1

For every , there exists a -container in of length .

Proof

Let be a -container between and in with length . Then this will also be a -container between and in . Let be the path , where and . Then, will be a -container between and in and the length of this container is .  □

Proposition 2.2

For and , there exists a -container in of length , where is the twin of .

Proof

Let and be a -container between and in . Let in . Then is a -container between and in and the length of this container is .  □

Proposition 2.3

For , there exists a -container in of length , where and are the twin of and respectively.

Proof

Let and , where . Consider a container in and replace and by and to form . Then is a -container between and in and is of length .  □

Proposition 2.4

For and , there exists a -container in of length 2 or 3.

Proof

Since in , every has at least neighbors in . Let , where . Then is a container of width at least in . If , this gives the required -container by considering any of the ’s. If , then will be the required -container. Thus, in this case is either 2 or 3.  □

Proposition 2.5

For and , there exists a -container in of length 4.

Proof

Let . Consider the paths for ,…, where and . For each , . Hence we are left with number of choices in the subsequent selection of as well as and therefore these paths are vertex disjoint. These paths, together with the edge will then form a -container in and the length of this container is 4.  □

Proposition 2.6

Let be a connected graph with . Then, between any two vertices there exists a container in of width such that .

Proof

Let .

Case 1:, .

In this case, by Lemma 1.2. We claim that for every , there exists a container of width in . For this, consider a path in , say . Corresponding to this path in , there are two vertex disjoint paths in , namely and or and (according as is even or odd). Thus any -container in will give a -container in . Any , paths from this container, will give a -container in of length at most in .

Case 2:, .

Here , by Lemma 1.3. Consider the -container obtained in Case 1 and include the path , where and to that container (such vertices and exist, as degree of both and is at least ). This is a container in of width and the length of this container is .  □

Proposition 2.7

Let be a connected graph with , . Then, between any two vertices there exists a container in of width such that .

Proof

For vertices in the result follows from Proposition 2.6 and in other cases, the proof is similar to that in Propositions 2.2^{Proposition 2.3}–2.5.  □

2.2 Wide diameter of the Mycielskian of a graph

Theorem 2.8

If is a connected graph, then

Proof

It follows from the propositions in Section 2.1, that . Now, to prove the reverse inequality, consider a pair of vertices such that . Then, and hence .  □

Corollary 2.9

If is a connected graph, then

3 Fault diameter of the Mycielskian of a graph

Theorem 3.1

Let be a connected graph with . Then .

Proof

Let . Then . Take the vertices , in which are at a distance , when vertices are deleted from . We claim that when vertices are deleted from , the maximum possible distance between and in is . For this, let with be deleted from . Then,

Case 1:.

In this case, or or intersects both and . If , then vertices in of are connected through their twins and maximum distance between and is 4. If , then maximum distance between and is . If intersects both and , then the distance between and is maximum when and the corresponding distance is . Thus in this case, the maximum possible distance between and is .

Case 2:.

If , then the distance between and is maximum, when the remaining vertices are deleted from and the corresponding distance is .

Thus we have a pair of vertices and in for which the maximum distance between them is , when vertices are deleted and therefore .

Next, we show that . For this, consider the following cases.

Case 1:.

In this case, becomes disconnected and the vertices in are connected by the path through ‘’. Therefore the maximum distance between them is 4. For all other pairs of vertices, maximum distance possible is less than 4.

Case 2:.

When all the vertices are deleted from , the maximum distance between any pair of vertices in and that between and is diam. For other pairs of vertices, the maximum distance is 3. Therefore, in this case diam() is .

Case 3: intersects both and .

In this case, the maximum distance occurs between the vertices in and the corresponding distance is

Case 4:.

If , then the remaining vertices can be deleted from , or from or from both. But in all these cases maximum distance possible is , which occurs when the vertices are deleted entirely from or from .

Thus we have and the result follows.  □

Corollary 3.2

Let be a connected graph with . Then , .

Theorem 3.3

Let be a connected graph with , , then .

Proof

Let and be any set of vertices. By Lemma 1.2, , . To determine , consider the following cases.

Case 1:.

In this case, , , or intersects both and . In any situation, the maximum distance possible is , which occurs when vertices from and the remaining vertices from are deleted.

Case 2:.

If , then the remaining vertices are to be deleted from . Now, we have the following sub cases.

Case 2a: The remaining vertices are deleted from .

In this case, the maximum distance occurs between those and , for which all the neighbors except one, belong to and the corresponding distance is 2 more than diam().

Case 2b: The remaining vertices are deleted from .

In this case, the paths in are unaffected and hence the distance between any pair of vertices in is same as that in . Thus the maximum possible distance is .

Case 2c: Some vertices are deleted from and the remaining from .

The maximum distance occurs when vertices from and from are deleted. Since any vertex has at least neighbors in , there exists at least one neighbor in for every . Thus the maximum possible distance between the vertices in this case is .

Hence .  □

Theorem 3.4

Let be a connected graph with , . Then .

Proof

In this case and the proof is similar to that of Theorem 3.3.  □

4 Diameter vulnerability of the Mycielskian of a graph

It may be noted that and hence we find , the maximum diameter of obtained by deleting edges, to study the diameter vulnerability of .

Theorem 4.1

Let be a connected graph with and . Then, .

Proof

To find , we consider the following cases of edge deletions.

Case 1: The deleted edges are of the form , where .

If the edges of the form are deleted, then the vertices in are connected by a path through the twins and . Therefore, they can be at a distance . The other distances are unaffected by this, except possibly that between any vertex and its twin . If the edges are deleted in such a way that the shortest path between and is affected, then the distance is 3 by using the path .

Case 2: The deleted edges are of the form , where and .

In this case, the distance between and is unaffected. If the edges deleted are of the form where , then distance between and its twin is affected and we have to take the path and hence the distance becomes 3. The distance between and is , as we have to consider either the path where is a path in or the path . The maximum possible distance between and occurs, when all the edges incident on the vertex with degree are deleted. Then, we have to take the path as , and hence the distance is 3. Thus if the edges of the form are deleted, then maximum , maximum , maximum and maximum .

Case 3: The deleted edges are of the form , where .

In this case maximum . The maximum possible distance between and is as we have to take the path , where and . Since has at least neighbors in both and maximum distance between and is 3 and that of and is also 3 by considering the path , and (such a exists as the minimum degree of any is ). Thus in this case, maximum , maximum , maximum .

Hence .  □

Corollary 4.2

If , then .

5 -dominating number of the Mycielskian of a graph

Lemma 5.1

If is a minimum -dominating set in , where , then .

Proof

Suppose that is a minimum -dominating set in and . Let and replace the path and the path in the respective containers by the paths (or ) and (or ) respectively, where and . There exist disjoint paths between and also. Thus becomes an -dominating set of , which contradicts the definition of .  □

Theorem 5.2

For a connected graph , , .

Proof

Case 1:. Let be a minimum -dominating set in , . Then we claim that is also an -dominating set in .

Clearly in . Now, consider the following cases.

Case 1a:.

Consider the -container in . To this container include a -path through disjoint with the paths already considered. This shows that every is -dominated by .

Case 1b:.

Let .

As , there exists a container of width at least namely , where . If , then this will give the required -container. Otherwise we have to take one more path through to get the required container.

If , then take the -container of width in , replace by and include the path and .

Case 1c:.

In this case, the set of all paths will be the required container if . If , then the required container is .

Thus is also an -dominating set in , and therefore .

Case 2:, . Let be a minimum -dominating set in . Then, corresponding to each path in the container in , we have two vertex disjoint paths in (Proposition 2.6) and it can be shown that is also a -dominating set in as in Case 1. Hence it follows that , .

To prove the reverse inequality consider a minimum -dominating set of , and define . Then is an -dominating set of and the fact that gives . □

Corollary 5.3

For a connected graph , , .

Notes

Peer review under responsibility of Kalasalingam University.