American Institute of Mathematical Sciences

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

Vulnerability of super connected split graphs and bisplit graphs

Litao Guo 1, and  Bernard L. S. Lin 2,,

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-$λ$.

Keywords: Split graphs, bisplit graphs, super connectivity, super edge connectivity.
Mathematics Subject Classification: Primary: 05C40; Secondary: 05C90.
Citation: Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete & 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.  Google Scholar

[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.  Google Scholar

[3]

S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297.  doi: 10.1016/S0012-365X(98)00156-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application, Academic Press, New York, 1976.  Google Scholar

[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.  Google Scholar

[3]

S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297.  doi: 10.1016/S0012-365X(98)00156-3.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

Figure 1.  $G$ is not super-$\kappa$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  $G$ is not super-$\lambda$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  $G$ is not super-$\lambda$
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  shuttle graph
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Birol Yüceoǧlu, ş. ilker Birbil, özgür Gürbüz. Dispersion with connectivity in wireless mesh networks. Journal of Industrial & 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 & 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 & Continuous Dynamical Systems, 2017, 37 (7) : 3567-3585. doi: 10.3934/dcds.2017153
[4]

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 & Optimization, 2014, 4 (1) : 49-58. doi: 10.3934/naco.2014.4.49
[5]

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
[6]

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 & Continuous Dynamical Systems, 2019, 39 (9) : 5185-5206. doi: 10.3934/dcds.2019211
[7]

Chi Po Choi, Xianfeng Gu, Lok Ming Lui. Subdivision connectivity remeshing via Teichmüller extremal map. Inverse Problems & Imaging, 2017, 11 (5) : 825-855. doi: 10.3934/ipi.2017039
[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 & 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 & 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 & 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 & 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 & 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 & 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 & 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

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences