Symmetry and two symmetry measures for the web and spider web graphs
- PDF / 483,110 Bytes
- 12 Pages / 439.37 x 666.142 pts Page_size
- 101 Downloads / 168 Views
Symmetry and two symmetry measures for the web and spider web graphs Somayeh Madani1 · Ali Reza Ashrafi1 Received: 7 April 2020 © Korean Society for Informatics and Computational Applied Mathematics 2020
Abstract Suppose G is a simple graph, ≤ Aut(G) and α ∈ . Define μ(G) = |V (G)| 2 u∈V (G),α∈ d(u, α(u)), η(G) = u∈V (G),α∈ (d(u, α(u))) , G P(G) = 2||
(G)| μ(G) and G P (2) (G) = 21 G P(G) + |V4|| η(G). The graph invariants G P(G) and (2) G P (G) are two recent measures for comparing symmetry of complex networks. The aim of this paper is to compute the symmetry of web and spider web graphs and then apply the structure of these groups to calculate the graph invariants G P(G) and G P (2) (G). These numbers help us to judge on the complexity of these networks.
Keywords Web graph · Spider web graph · Graovac–Pisanski index Mathematics Subject Classification 05C12 · 20B25 · 68M11
1 Basic definitions Unless otherwise mentioned, we suppose throughout this paper that all graphs are simple. If G is such a graph, then the vertex and edge sets of G are denoted by V (G) and E(G), respectively. An edge connecting vertices x and y in G is denoted by x − y. An automorphism α of G is a permutation on V (G) such that uv ∈ E(G) if and only if α(u)α(v) ∈ E(G). There is a natural action of G on V (G) and the equivalence classes of this action are called the orbits of G on V (G). If there is only one orbit then the graph is called vertex transitive. The Wiener index of a graph G, W (G), is the oldest distance-based graph invariant defined as the sum of distances between all pair of vertices in G [28]. Here, the distance between two vertices u and v, d(u, v), is defined as the length of a shortest path connecting u and v. Harold Wiener who was a chemist used the name path number
B 1
Ali Reza Ashrafi [email protected] Department of Pure Mathematics, Faculty of Mathematical Sciences, University of Kashan, Kashan, Iran
123
S. Madani, A. R. Ashrafi
for this invariant and in the chemistry language, he defined the path number of a alkane molecule M as the sum of all distance between any two carbon atoms in M in terms of carbon-carbon bonds. After finding many applications for this graph invariant in chemistry, Randi´c [24] introduced another distance-based graph invariant that now a days named hyper-Wiener index. This number is defined as W W (G) = 21 W (G) + 1 2 {u,v}⊆V (G) d(u, v) . 2 Graovac and Pisanski [11] generalized the concept of Wiener index by an algebraic approach. In an exact phrase, suppose is a subgroup of the full automorphism group Aut(G). Then the Graovac–Pisanski index (G P index for short) of G with respect (G)| to is defined as G P(G) = |V2|| u∈V (G) α∈ d(u, α(u)). If we define μ(G) = |V (G)| d(u, α(u)), then G P(G) = u∈V (G),α∈ 2|| μ(G). It is merit to say that Graovac and Pisanski used the name modified Wiener index for this graph invariant and one of the present authors (ARA) called this invariant symmetry-moderated Wiener index [25]. Ghorbani and Klavˇzar [10] invited other resea
Data Loading...
