An improved upper bound for the order of mixed graphs

All of RECERCAT

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

Title:	An improved upper bound for the order of mixed graphs
Author:	Dalfó Simó, Cristina; Fiol Mora, Miquel Àngel; López Lorenzo, Nacho
Other authors:	Universitat Politècnica de Catalunya. Departament de Matemàtiques; Universitat Politècnica de Catalunya. COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
Abstract:	A mixed graph G can contain both (undirected) edges and arcs (directed edges). Here we derive an improved Moore-like bound for the maximum number of vertices of a mixed graph with diameter at least three. Moreover, a complete enumeration of all optimal (1, 1)-regular mixed graphs with diameter three is presented, so proving that, in general, the proposed bound cannot be improved.
Subject(s):	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Graph theory -Mixed graph -Moore bound -Network design -Degree/diameter problem -Grafs, Teoria de
Rights:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Document type:	Article - Submitted version Article
Share: