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ätP. L. HammerV. 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. GuoC. 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. GuoW. 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. ZhangQ. 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ätP. L. HammerV. 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. GuoC. 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. GuoW. 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. ZhangQ. 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.

Figure 1.  $G$ is not super-$\kappa$
Figure 2.  $G$ is not super-$\lambda$
Figure 3.  $G$ is not super-$\lambda$
Figure 4.  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

Article outline

Figures and Tables

[Back to Top]