Neighbor-connectivity of pancake networks and burnt pancake networks. (English) Zbl 1535.68235
Summary: The vertex-neighbor-connectivity \(\kappa_\mathrm{NB}(G)\) is the minimum cardinality of a vertex subset in \(G\), the deleting of whose closed neighborhood causes \(G\) to be disconnected, complete, or empty; the edge-neighbor-connectivity \(\lambda_\mathrm{NB}(G)\) is the minimum cardinality of an edge subset in \(G\), the deleting of whose ends causes \(G\) to be disconnected, trivial (a single vertex), or empty. In this paper, we determine the vertex (resp. edge)-neighbor-connectivity of pancake networks \(P_n\) (\(n \geq 2\)) and burnt pancake networks \(BP_n\) (\(n \geq 1\)).
Keywords:
edge-neighbor-connectivity; vertex-neighbor-connectivity; pancake networks; burnt pancake networksReferences:
| [1] | Akers, S. B.; Krishnamurthy, B., A group-theoretic model for symmetric interconnection networks, IEEE Trans. Comput., 38, 4, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer: Springer New York · Zbl 1134.05001 |
| [3] | Blanco, S. A.; Buehrle, C.; Patidar, A., Cycles in the burnt pancake graph, Discrete Appl. Math., 271, 1-14 (2019) · Zbl 1428.05129 |
| [4] | Cozzens, M. B.; Wu, S. S.Y., Extreme values of the edge-neighbor-connectivity, Ars Comb., 39, 199-210 (1995) · Zbl 0833.05055 |
| [5] | Compeau, P. E.C., Girth of pancake graphs, Discrete Appl. Math., 159, 1641-1645 (2011) · Zbl 1228.05166 |
| [6] | Chen, Y.-C.; Tan, J. J.M., Restricted connectivity for three families of interconnection networks, Appl. Math. Comput., 188, 1848-1855 (2007) · Zbl 1120.68079 |
| [7] | Doty, L. L., A new bound for neighbor-connectivity of abelian Cayley graphs, Discrete Math., 306, 1301-1316 (2006) · Zbl 1098.05047 |
| [8] | Doty, L. L.; Goldstone, R. J.; Suffel, C. L., Cayley graphs with neighbor connectivity one, SIAM J. Discrete Math., 9, 625-642 (1996) · Zbl 0862.05050 |
| [9] | Dvořák, T.; Gu, M. M., Neighbor connectivity of k-ary n-cubes, Appl. Math. Comput., 379, 1-9 (2020) · Zbl 1460.05099 |
| [10] | Fàbrega, J.; Fiol, M. A., On the extraconnectivity of graphs, Discrete Math., 155, 49-57 (1996) · Zbl 0857.05064 |
| [11] | Gunther, G., Neighbor-connected in regular graphs, Discrete Appl. Math., 11, 233-243 (1985) · Zbl 0591.05048 |
| [12] | Gunther, G.; Hartnell, B., On minimizing the effects of betrayals in a resistance movement, (Proc. 8th Manitoba Conf. on Numer. Math. Comp. (1978)), 285-306 · Zbl 0405.05045 |
| [13] | Gunther, G.; Hartnell, B.; Nowakowski, R., Neighbor-connected graphs and projective planes, Networks, 17, 241-247 (1987) · Zbl 0654.05050 |
| [14] | Hoffman, C. M., Group Theoretic Algorithm and Graph Isomorphism (1982), Springer Verlag: Springer Verlag New York · Zbl 0487.68055 |
| [15] | Kanevsky, A.; Feng, C., On the embedding of cycles in pancake graphs, Parallel Comput., 21, 923-936 (1995) · Zbl 0875.68708 |
| [16] | Konstantinova, E. V.; Medvedev, A. N., Small cycles in the pancake graph, Ars Math. Contemp., 7, 237-246 (2014) · Zbl 1301.05126 |
| [17] | Lv, M. J.; Fan, J. X.; Zhou, J. Y.; Cheng, B. L.; Jia, X. H., The extra connectivity and extra diagnosability of regular interconnection networks, Theor. Comput. Sci., 809, 88-102 (2020) · Zbl 1436.68050 |
| [18] | Song, S. L.; Li, X. Y.; Zhou, S. M.; Chen, M., Fault tolerance and diagnosability of burnt pancake networks under the comparison model, Theor. Comput. Sci., 582, 48-59 (2015) · Zbl 1309.68021 |
| [19] | Shang, Y. J.; Hao, R.-X.; Gu, M.-M., Neighbor connectivity of two kinds of Cayley graphs, Acta Math. Appl. Sin. Engl. Ser., 34, 386-397 (2018) · Zbl 1387.05134 |
| [20] | Wu, S. S.Y.; Cozzens, M. B., The minimum size of critically m-neighbor-connected graphs, Ars Comb., 29, 149-160 (1990) · Zbl 0706.05032 |
| [21] | Zhao, X. B.; Zhang, Z.; Ren, Q., Edge neighbor connectivity of Cartesian product graph \(G \times K_2\), Appl. Math. Comput., 217, 5508-5511 (2011) · Zbl 1209.05136 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
