首页 | 本学科首页   官方微博 | 高级检索  
     检索      


A new forbidden pair for 6-contractible edges
Authors:Kiyoshi Ando
Institution:National Institute of Informatics, JST ERATO Kawarabayashi Large Graph Project, Global Research Center for Big Data Mathematics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan
Abstract:An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. If every k-connected graph with no k-contractible edge has either H1 or H2 as a subgraph, then an unordered pair of graphs {H1,H2} is said to be a forbidden pair for k-contractible edges. We prove that {K1+3K2,K1+(P3K2)} is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.
Keywords:6-connected graph  6-contractible edge  Forbidden subgraph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号