Graphic Sequences and Split Graphs

The split graph Kr∨Ks on r＋s vertices is denoted by Sr,s A graphic sequence π = （d1, d2, …, dn） is said to be potentially Sr,s-graphic if there is a realization of π containing Sr,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially Sr,s-graphic is obtained, which ex...

Full description

Saved in:
Bibliographic Details
Published in:Acta Mathematicae Applicatae Sinica 2016-10, Vol.32 (4), p.1005-1014
Main Authors: Yin, Jian-hua, Meng, Lei, Yin, Meng-Xiao
Format: Article
Language:English
Subjects:
Applications of Mathematics
Graph theory
Math
Math Applications in Computer Science
Mathematical and Computational Physics
Mathematics
Mathematics and Statistics
Theoretical
充分条件
分裂图
图形
序列
顶点
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The split graph Kr∨Ks on r＋s vertices is denoted by Sr,s A graphic sequence π = （d1, d2, …, dn） is said to be potentially Sr,s-graphic if there is a realization of π containing Sr,s as a subgraph. In this paper, a simple sufficient condition for π to be potentially Sr,s-graphic is obtained, which extends an analogous condition for π to be potentially Kr＋1-graphic due to Yin and Li （Discrete Math. 301 （2005） 218-227）. As an application of this condition, we further determine the values of δ（Sr,s, n） for n _≥3＋ 3s - 1.
ISSN:0168-9673
1618-3932
DOI:10.1007/s10255-016-0622-5