American Institute of Mathematical Sciences

August & September  2019, 12(4&5): 1179-1185. doi: 10.3934/dcdss.2019081

Vulnerability of super connected split graphs and bisplit graphs

 1 School of Applied Mathematics, Xiamen University of Technology, Xiamen, Fujian 361024, China 2 School of Science, Jimei University, Xiamen, Fujian 361021, China

* Corresponding author: Bernard L. S. Lin

Received  July 2017 Revised  January 2018 Published  November 2018

A graph $G = (C, I, E)$ is called a split graph if its vertex set $V$ can be partitioned into a clique $C$ and an independent set $I$. A graph $G = (Y \cup Z, I, E)$ is called a bisplit graph if its vertex set $V$ can be partitioned into three stable sets $I, Y,Z$ such that $Y \cup Z$ induces a complete bipartite graph and an independent set $I$. A connected graph $G$ is called supper-$κ$ (resp. super-$λ$) if every minimum vertex cut (edge cut) of $G$ is the set of neighbors of some vertex (the edges of incident to some vertex) in $G$. In this note, we show that: split graphs and bisplit graphs are super-$κ$ and super-$λ$.

Citation: Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1179-1185. doi: 10.3934/dcdss.2019081
References:
 [1] J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application, Academic Press, New York, 1976. [2] A. Brandstät, P. L. Hammer, V. B. Le and V. V. Lozin, Bisplit graphs, Discrete Math., 299 (2005), 11-32.  doi: 10.1016/j.disc.2004.08.046. [3] S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315. [4] L. T. Guo, C. Qin and X. F. Guo, Super connectivity of Kronecker products of graphs, Information Processing Letters, 110 (2010), 659-661.  doi: 10.1016/j.ipl.2010.05.013. [5] L. T. Guo, W. Yang and X., F. Guo, Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs, Applied Mathematics Letters, 26 (2013), 120-123.  doi: 10.1016/j.aml.2012.04.006. [6] M. Metsidik and E. Vumar, Edge vulnerability parameters of bisplit graphs, Computers and Mathematics with Applications, 56 (2008), 1741-1747.  doi: 10.1016/j.camwa.2008.04.015. [7] G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297.  doi: 10.1016/S0012-365X(98)00156-3. [8] S. Zhang, Q. Zhang and H. Yang, Vulnerability parameters of split graphs, Int. J. Comput. Math., 85 (2008), 19-23.  doi: 10.1080/00207160701365721. [9] Q. Zhang and S. Zhang, Edge vulnerability parameters of split graphs, Applied Mathematics Letters, 19 (2006), 916-920.  doi: 10.1016/j.aml.2005.09.011.

show all references

References:
 [1] J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application, Academic Press, New York, 1976. [2] A. Brandstät, P. L. Hammer, V. B. Le and V. V. Lozin, Bisplit graphs, Discrete Math., 299 (2005), 11-32.  doi: 10.1016/j.disc.2004.08.046. [3] S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315. [4] L. T. Guo, C. Qin and X. F. Guo, Super connectivity of Kronecker products of graphs, Information Processing Letters, 110 (2010), 659-661.  doi: 10.1016/j.ipl.2010.05.013. [5] L. T. Guo, W. Yang and X., F. Guo, Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs, Applied Mathematics Letters, 26 (2013), 120-123.  doi: 10.1016/j.aml.2012.04.006. [6] M. Metsidik and E. Vumar, Edge vulnerability parameters of bisplit graphs, Computers and Mathematics with Applications, 56 (2008), 1741-1747.  doi: 10.1016/j.camwa.2008.04.015. [7] G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297.  doi: 10.1016/S0012-365X(98)00156-3. [8] S. Zhang, Q. Zhang and H. Yang, Vulnerability parameters of split graphs, Int. J. Comput. Math., 85 (2008), 19-23.  doi: 10.1080/00207160701365721. [9] Q. Zhang and S. Zhang, Edge vulnerability parameters of split graphs, Applied Mathematics Letters, 19 (2006), 916-920.  doi: 10.1016/j.aml.2005.09.011.
$G$ is not super-$\kappa$
$G$ is not super-$\lambda$
$G$ is not super-$\lambda$
shuttle graph
 [1] Birol Yüceoǧlu, ş. ilker Birbil, özgür Gürbüz. Dispersion with connectivity in wireless mesh networks. Journal of Industrial and Management Optimization, 2018, 14 (2) : 759-784. doi: 10.3934/jimo.2017074 [2] Cristina Cross, Alysse Edwards, Dayna Mercadante, Jorge Rebaza. Dynamics of a networked connectivity model of epidemics. Discrete and Continuous Dynamical Systems - B, 2016, 21 (10) : 3379-3390. doi: 10.3934/dcdsb.2016102 [3] Canela Jordi. Singular perturbations of Blaschke products and connectivity of Fatou components. Discrete and Continuous Dynamical Systems, 2017, 37 (7) : 3567-3585. doi: 10.3934/dcds.2017153 [4] Youming Wang, Fei Yang, Song Zhang, Liangwen Liao. Escape quartered theorem and the connectivity of the Julia sets of a family of rational maps. Discrete and Continuous Dynamical Systems, 2019, 39 (9) : 5185-5206. doi: 10.3934/dcds.2019211 [5] Chi Po Choi, Xianfeng Gu, Lok Ming Lui. Subdivision connectivity remeshing via Teichmüller extremal map. Inverse Problems and Imaging, 2017, 11 (5) : 825-855. doi: 10.3934/ipi.2017039 [6] Shuangliang Tian, Ping Chen, Yabin Shao, Qian Wang. Adjacent vertex distinguishing edge-colorings and total-colorings of the Cartesian product of graphs. Numerical Algebra, Control and Optimization, 2014, 4 (1) : 49-58. doi: 10.3934/naco.2014.4.49 [7] David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97 [8] Srimathy Srinivasan, Andrew Thangaraj. Codes on planar Tanner graphs. Advances in Mathematics of Communications, 2012, 6 (2) : 131-163. doi: 10.3934/amc.2012.6.131 [9] Cristina M. Ballantine. Ramanujan type graphs and bigraphs. Conference Publications, 2003, 2003 (Special) : 78-82. doi: 10.3934/proc.2003.2003.78 [10] Daniele D'angeli, Alfredo Donno, Michel Matter, Tatiana Nagnibeda. Schreier graphs of the Basilica group. Journal of Modern Dynamics, 2010, 4 (1) : 167-205. doi: 10.3934/jmd.2010.4.167 [11] James B. Kennedy, Jonathan Rohleder. On the hot spots of quantum graphs. Communications on Pure and Applied Analysis, 2021, 20 (9) : 3029-3063. doi: 10.3934/cpaa.2021095 [12] Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete and Continuous Dynamical Systems, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291 [13] Tomasz Dlotko, Tongtong Liang, Yejuan Wang. Critical and super-critical abstract parabolic equations. Discrete and Continuous Dynamical Systems - B, 2020, 25 (4) : 1517-1541. doi: 10.3934/dcdsb.2019238 [14] Shu-Yu Hsu. Super fast vanishing solutions of the fast diffusion equation. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5383-5414. doi: 10.3934/dcds.2020232 [15] A. M. Micheletti, Monica Musso, A. Pistoia. Super-position of spikes for a slightly super-critical elliptic equation in $R^N$. Discrete and Continuous Dynamical Systems, 2005, 12 (4) : 747-760. doi: 10.3934/dcds.2005.12.747 [16] Dina Ghinelli, Jennifer D. Key. Codes from incidence matrices and line graphs of Paley graphs. Advances in Mathematics of Communications, 2011, 5 (1) : 93-108. doi: 10.3934/amc.2011.5.93 [17] Wooyeon Kim, Seonhee Lim. Notes on the values of volume entropy of graphs. Discrete and Continuous Dynamical Systems, 2020, 40 (9) : 5117-5129. doi: 10.3934/dcds.2020221 [18] Renato Iturriaga, Héctor Sánchez Morgado. The Lax-Oleinik semigroup on graphs. Networks and Heterogeneous Media, 2017, 12 (4) : 643-662. doi: 10.3934/nhm.2017026 [19] Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18. [20] Deng Lu, Maria De Iorio, Ajay Jasra, Gary L. Rosner. Bayesian inference for latent chain graphs. Foundations of Data Science, 2020, 2 (1) : 35-54. doi: 10.3934/fods.2020003

2020 Impact Factor: 2.425

Tools

Article outline

Figures and Tables