The clique-transversal number of a {K1,3,K4}-free 4-regular graph

Autor:	Qinqin Li, Fenling Xu, Baoyindureng Wu
Rok vydání:	2015
Předmět:	Combinatorics Discrete mathematics Graph power k-vertex-connected graph Discrete Mathematics and Combinatorics Bound graph Graph toughness Clique graph Distance-regular graph Graph factorization Simplex graph Theoretical Computer Science Mathematics
Zdroj:	Discrete Mathematics. 338:1126-1130
ISSN:	0012-365X
Popis:	A clique of a graph G is a complete subgraph maximal under inclusion and having at least two vertices. A clique-transversal set D of a graph G is a set of vertices of G such that D meets all cliques of G . The clique-transversal number, denoted by ? c ( G ) , is the cardinality of a minimum clique-transversal set in G . Wang et?al. (2014) proved that ? c ( G ) = ? n 3 ? for any 2-connected { K 1 , 3 , K 4 } -free 4-regular graph of order n , and conjectured that ? c ( G ) ? 10 n + 3 27 for a connected { K 1 , 3 , K 4 } -free 4-regular graph of order n .In this paper, we give a short proof of the aforementioned theorem of Wang et?al. and show that the above conjecture is true, apart from only three exceptions.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::df09a36fc9b7690523da4b57070e0463 https://doi.org/10.1016/j.disc.2015.01.039 Zobrazit plný text záznamu Full Text from ScienceDirect