1. Introduction
In this paper, by a graph we mean a simple graph. For notation and terminology, we refer to [1]. Devaraj and Sukumaran [2] introduced the concept of the vertex polynomial of graphs. The vertex set is denoted by V(G) and the edge set by E(G). For v ∈ V, deg(v) is the number of edges incident with v, and the maximum degree of G is defined as Δ(G) = max{deg(v) / v ∈ V}. In this paper, we find the vertex polynomials of the vertex switchings of some graphs. The graph G = (V, E) is simply denoted by G. The concept of switching was introduced by Seidel [3]. We refer to [4] for more results on vertex switching. The vertex switching Gv of a graph G is the graph obtained by taking a vertex v of G, removing all the edges incident to v and adding edges joining v to every other vertex that is not adjacent to v in G.
2. Main Results
Theorem 2.1. The vertex polynomial of the graph obtained by switching a vertex of a cycle Cn is V(G, x) = xn−3 + (n − 3)x3 + 2x.
Proof. Let G denote the graph obtained by switching a vertex of the cycle Cn, and let the vertex v1 be switched. Then the end vertices v2 and vn have degree 1. The vertex v1 is adjacent to (n − 3) vertices and so has degree (n − 3). The remaining (n − 3) vertices will have degree 3. Hence V(G, x) = xn−3 + (n − 3)x3 + 2x.
We now consider the switching of the wheel graph Wn. Here two types of switching can be considered, one being the switching of a rim vertex and the other the switching of the central vertex. Switching the central vertex results in an isolated vertex, so we consider only the switching of a rim vertex in the wheel Wn.
Theorem 2.2. The vertex polynomial of the graph obtained by switching a rim vertex of a wheel Wn is V(G, x) = 2xn−3 + (n − 3)x4 + 2x.
Proof. Let G denote the graph obtained by switching a rim vertex in the wheel Wn. Without loss of generality, let us assume that the vertex v1 is switched, as shown in Fig. 3.
Since the vertex v1 is switched, it is adjacent to (n − 3) vertices, and so it has degree (n − 3). Now the end vertices have degree 1 and the remaining (n − 3) vertices have degree 4.
Considering all these, the vertex polynomial is V(G, x) = 2xn−3 + (n − 3)x4 + 2x.
Theorem 2.3. The vertex polynomial of the graph obtained by switching a vertex of a gear graph Gn is
Proof.
Case 1. Let us assume that the central vertex is switched.
When the central vertex is switched, it results in a wheel graph. So the vertex polynomial is V(G, x) = xn + nx3 + nx2.
Case 2. Let us assume that a vertex of degree 2 is switched.
Without loss of generality, let us assume that the vertex u1 is switched. When the vertex u1 is switched, it is adjacent to 2(n − 1) vertices and hence has degree 2(n − 1). The central vertex will receive degree (n + 1). The two end vertices will have degree 2. The remaining (n − 2) and (n − 1) vertices will have degrees 4 and 3, respectively. Hence the vertex polynomial obtained here is V(G, x) = x2(n−1) + xn+1 + (n − 2)x4 + (n − 1)x3 + 2x2.
Case 3. Let us assume that a vertex of degree 3 is switched.
Without loss of generality, let us assume that the vertex v1 is switched. When the vertex v1 is switched, it is adjacent to (2n − 3) vertices and hence has degree (2n − 3). The central vertex will receive degree (n − 1). The two end vertices will have degree 1. The remaining (n − 1) and (n − 2) vertices will have degrees 4 and 3, respectively. Hence the vertex polynomial obtained here is V(G, x) = x2n−3 + xn−1 + (n − 1)x4 + (n − 2)x3 + 2x.
In the following theorem, we consider the switching of the helm graph Hn. Here we can consider only two cases: in the first case we switch the apex vertex, and in the second case we switch an outer rim vertex. When we switch an inner rim vertex, the graph becomes disconnected.
Theorem 2.4. The vertex polynomial of the graph obtained by switching a vertex of a helm graph Hn is
Proof.
Case 1. Let us assume that the central vertex is switched.
When the central vertex of a helm graph is switched, it will be adjacent to n vertices, so that it receives degree n. The n inner vertices have degree 3 and the n outer vertices have degree 2.
Hence the vertex polynomial is V(G, x) = xn + nx3 + nx2.
Case 2. Switching an outer rim vertex ui, 1 ≤ i ≤ n.
Without loss of generality, let us assume that the vertex u1 is switched. Then it will be adjacent to (2n − 2) vertices and so it has degree (2n − 2). The central vertex is adjacent to n vertices. An inner rim vertex has degree 3 and the remaining (n − 1) inner rim vertices have degree 5. The (n − 1) outer rim vertices have degree 2. Hence the vertex polynomial is V(G, x) = x2n−2 + xn + (n − 1)x5 + (n − 1)x + x3.
3. Conclusion
The vertex polynomials of a few simple switched graphs have been found. This can be applied to any switched graph. These vertex polynomials of switched graphs have wide applications in circuit design, traffic flow, social network analysis, computer network security, optimisation, graph dynamics, etc.
References
- Harary F. Graph theory. Narosa Publishing House; 1969.
- Devaraj J, Sukumaran E. On vertex polynomial. Int J Math Sci Eng Appl. 2012;6(1):371–80.
- Seidel JJ. A survey of two-graphs. In: Colloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I. Rome: Accademia Nazionale dei Lincei; 1976. p. 481–511. (Atti dei Convegni Lincei; no. 17).
- Maya P, Nicholas T. Duplication and switching of divisor cordial graphs. Am Rev Math Stat. 2016 Dec;4(2):18–29. https://doi.org/10.15640/arms.v4n2a3