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 & Continuous Dynamical Systems - S, 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 & 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 - A, 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]

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

[7]

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

[8]

Cristina M. Ballantine. Ramanujan type graphs and bigraphs. Conference Publications, 2003, 2003 (Special) : 78-82. doi: 10.3934/proc.2003.2003.78

[9]

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

[10]

Yong Lin, Gábor Lippner, Dan Mangoubi, Shing-Tung Yau. Nodal geometry of graphs on surfaces. Discrete & Continuous Dynamical Systems - A, 2010, 28 (3) : 1291-1298. doi: 10.3934/dcds.2010.28.1291

[11]

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 - A, 2005, 12 (4) : 747-760. doi: 10.3934/dcds.2005.12.747

[12]

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

[13]

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

[14]

Thomas Zaslavsky. Quasigroup associativity and biased expansion graphs. Electronic Research Announcements, 2006, 12: 13-18.

[15]

Xiangjin Xu. Multiple solutions of super-quadratic second order dynamical systems. Conference Publications, 2003, 2003 (Special) : 926-934. doi: 10.3934/proc.2003.2003.926

[16]

Alain Bensoussan, Jens Frehse. On diagonal elliptic and parabolic systems with super-quadratic Hamiltonians. Communications on Pure & Applied Analysis, 2009, 8 (1) : 83-94. doi: 10.3934/cpaa.2009.8.83

[17]

Christian Bonatti, Lorenzo J. Díaz, Todd Fisher. Super-exponential growth of the number of periodic orbits inside homoclinic classes. Discrete & Continuous Dynamical Systems - A, 2008, 20 (3) : 589-604. doi: 10.3934/dcds.2008.20.589

[18]

Wenxiong Chen, Congming Li. Super polyharmonic property of solutions for PDE systems and its applications. Communications on Pure & Applied Analysis, 2013, 12 (6) : 2497-2514. doi: 10.3934/cpaa.2013.12.2497

[19]

Xumin Gu. Global wellposedness for a transport equation with super-critial dissipation. Communications on Pure & Applied Analysis, 2011, 10 (2) : 653-665. doi: 10.3934/cpaa.2011.10.653

[20]

Qinqin Zhang. Homoclinic orbits for discrete Hamiltonian systems with local super-quadratic conditions. Communications on Pure & Applied Analysis, 2019, 18 (1) : 425-434. doi: 10.3934/cpaa.2019021

2017 Impact Factor: 0.561

Metrics

  • PDF downloads (3)
  • HTML views (58)
  • Cited by (0)

Other articles
by authors

[Back to Top]