no. 4
On the super connectivity of direct product of graphs
RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2767-2773

A vertex-cut S is called a super vertex-cut if G − S is disconnected and it contains no isolated vertices. The super-connectivity, κ′, is the minimum cardinality over all super vertex-cuts. This article provides bounds for the super connectivity of the direct product of an arbitrary graph and the complete graph K$$. Among other results, we show that if G is a non-complete graph with girth(G) = 3 and κ′(G) = ∞, then κ′(G × K$$) ≤ min{mn − 6, m(n − 1) + 5, 5n + m − 8}, where |V(G)| = m.

DOI : 10.1051/ro/2022085
Classification : 05C40, 05C82, 05C25
Keywords: Direct product, super connectivity, vertex-cut 
@article{RO_2022__56_4_2767_0,
     author = {Soliemany, Farnaz and Ghasemi, Mohsen and Varmazyar, Rezvan},
     title = {On the super connectivity of direct product of graphs},
     journal = {RAIRO. Operations Research},
     pages = {2767--2773},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {4},
     doi = {10.1051/ro/2022085},
     mrnumber = {4469505},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022085/}
}
TY  - JOUR
AU  - Soliemany, Farnaz
AU  - Ghasemi, Mohsen
AU  - Varmazyar, Rezvan
TI  - On the super connectivity of direct product of graphs
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 2767
EP  - 2773
VL  - 56
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022085/
DO  - 10.1051/ro/2022085
LA  - en
ID  - RO_2022__56_4_2767_0
ER  - 
%0 Journal Article
%A Soliemany, Farnaz
%A Ghasemi, Mohsen
%A Varmazyar, Rezvan
%T On the super connectivity of direct product of graphs
%J RAIRO. Operations Research
%D 2022
%P 2767-2773
%V 56
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022085/
%R 10.1051/ro/2022085
%G en
%F RO_2022__56_4_2767_0
Soliemany, Farnaz; Ghasemi, Mohsen; Varmazyar, Rezvan. On the super connectivity of direct product of graphs. RAIRO. Operations Research, Tome 56 (2022) no. 4, pp. 2767-2773. doi: 10.1051/ro/2022085

[1] J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. Elsevier, New York (1967). | MR

[2] G. B. Ekinci and J. B. Gauci, The super-connectivity of odd graphs and of their kronecker double cover. RAIRO-Oper. Res. 55 (2021) 561–566. | MR | Zbl | Numdam

[3] G. B. Ekinci and A. Kirlangiç, Super connectivity of kronecker product of complete bipartite graphs and complete graphs. Disc. Math. 339 (2016) 1950–1953. | MR | DOI

[4] G. B. Ekinci and A. Kirlangiç, The super edge connectivity of Kronecker product graphs. RAIRO-Oper. Res. 52 (2018) 561–566. | MR | Zbl | Numdam | DOI

[5] S. Ghozati, A finite automata approach to modeling the cross product of interconnection networks. Math. Compute. Model. 30 (1999) 185–200. | MR | DOI

[6] R. Guji and E. Vumar, A note on the connectivity of kronecker products of graphs. Appl. Math. Lett. 22 (2009) 1360–1363. | MR | DOI

[7] L. Guo and X. Guo, Super connectivity of Kronecker products of some graphs. Ars Combin. 123 (2015) 65–73. | MR

[8] L. Guo, C. Qin and X. Guo, Super connectivity of kronecker products of graphs. Inf. Process. Lett. 110 (2010) 659–661. | MR | DOI

[9] L. Guo, W. Yang and X. Guo, Super-connectivity of kronecker products of split graphs, powers of cycles, powers of paths and complete graphs. Appl. Math. Lett. 26 (2013) 120–123. | MR | DOI

[10] Kh Kamyab, M. Ghasemi and R. Varmazyar, Super connectivity of lexicographic product graphs. Ars Combin. Preprint [math.GR]. | arXiv

[11] R. Lammprey and B. Barnes, Products of graphs and applications. Model. Simul. 5 (1974) 1119–1123. | MR

[12] J. Leskovec, D. Chakrabarti, J. Kleinberg, C. Faloutsos and Z. Ghahramani, Kronecker graphs: An approach to modeling networks. J. Mach. Learn. Res. 11 (2010) 985–1042. | MR

[13] M. Lü, C. Wu, G. L. Chen and C. Lv, On super connectivity of cartesian product graphs. Networks 52 (2008) 78–87. | MR | DOI

[14] M. Ma, G. Liu and J. M. Xu, The super connectivity of augmented cubes. Inf. Process. Lett. 106 (2008) 59–63. | MR | DOI

[15] D. J. Miller, The categorical product of graphs. Can. J. Math. 20 (1968) 1511–1521. | MR | DOI

[16] F. Soliemany, M. Ghasemi and R. Varmazyar, Super connectivity of a family of direct product graphs. Int. J. Comput. Math. Comput. Syst. Theory 7 (2021) 1–5. | MR

[17] P. M. Weichsel, The kronecker product of graphs. Proc. Am. Math. Soc. 13 (1962) 47–52. | MR | DOI

[18] J. M. Xu, Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht (2001).

[19] J. M. Xu, M. Lü, M. Ma and A. Hellwig, Super connectivity of line graphs. Inf. Process. Lett. 94 (2005) 191–195. | MR | DOI

[20] C. S. Yang, J. F. Wang, J. Y. Lee and F. T. Boesch, Graph theoretic reliable analysis for the Boolean n -cube networks. IEEE Trans. Circuits Syst. 35 (1988) 1175–1179. | MR | DOI

[21] C. S. Yang, J. F. Wang, J. Y. Lee and F. T. Boesch, The number of spanning trees of the regular networks. Int. J. Comput. Math. 23 (1988) 185–200. | DOI

[22] J. X. Zhou, Super connectivity of direct product of graphs. Ars Math. Contemp. 8 (2015) 235–244. | MR | DOI

Cité par Sources :