Defensive alliances in regular graphs and circulant graphs

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/2284

dc.contributor	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV
dc.contributor	Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
dc.contributor.author	Araujo Pardo, M. Gabriela
dc.contributor.author	Barrière Figueroa, Eulalia
dc.date	2008-10
dc.identifier.uri	http://hdl.handle.net/2117/2284
dc.language.iso	eng
dc.relation	MTM2005-08990-C02-01
dc.relation	TEC2005-03575
dc.relation	2005SGR00256
dc.rights	Attribution-NonCommercial-NoDerivs 2.5 Spain
dc.rights	info:eu-repo/semantics/openAccess
dc.rights	http://creativecommons.org/licenses/by-nc-nd/2.5/es/
dc.subject	Graph theory
dc.subject	alliance
dc.subject	induced subgraph
dc.subject	Grafs, Teoria de
dc.subject	Classificació AMS::05 Combinatorics::05C Graph theory
dc.title	Defensive alliances in regular graphs and circulant graphs
dc.type	info:eu-repo/semantics/draft
dc.type	info:eu-repo/semantics/article
dc.description.abstract	In this paper we study defensive alliances in some regular graphs. We determine which subgraphs could a critical defensive alliance of a graph $G$ induce, if $G$ is $6$-regular and the cardinality of the alliance is at most $8$. In particular, we study the case of circulant graphs, i.e. Cayley graphs on a cyclic group. The critical defensive alliances of a circulant graph of degree at most $6$ are completely determined. For the general case, we give tight lower and upper bounds on the alliance number of a circulant graph with $d$ generators.