Sequence mixed graphs

DOI10.1016/J.DAM.2016.10.030MaRDI QIDQ505431zbMATH OpenOpenAlexFDO

Authors C. Dalfó, Nacho López, Miquel Angel Fiol

Publication date 23 January 2017

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.02863, http://hdl.handle.net/10459.1/59089

zbMATH Keywords

degree/diameter problemdiameterline digraphmean distancemixed graphMoore boundsequence graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A mixed graph can be seen as a type of digraph containing some edges (two opposite arcs). Here we introduce the concept of sequence mixed graphs, which is a generalization of both sequence graphs and iterated line digraphs. These structures are proven to be useful in the problem of constructing dense graphs or digraphs, and this is related to the degree/diameter problem. Thus, our generalized approach gives rise to graphs that have also good ratio order/diameter. Moreover, we propose a general method for obtaining a sequence mixed digraph by identifying some vertices of a certain iterated line digraph. As a consequence, some results about distance-related parameters (mainly, the diameter and the average distance) of sequence mixed graphs are presented.

Recommendations

• A construction of dense mixed graphs of diameter 2
• A family of mixed graphs with large order and diameter 2
• On bipartite‐mixed graphs
• Construction of extremal mixed graphs of diameter two
• An improved upper bound for the order of mixed graphs

Cites work

• A revised Moore bound for mixed graphs
• scientific article; zbMATH DE number 3859160 (Why is no real title available?)
• scientific article; zbMATH DE number 3632534 (Why is no real title available?)
• scientific article; zbMATH DE number 1242264 (Why is no real title available?)
• Line Digraph Iterations and the (d, k) Digraph Problem
• Moore bound for mixed networks
• New mixed Moore graphs and directed strongly regular graphs
• Non existence of some mixed Moore graphs of diameter 2 using SAT
• On mixed almost Moore graphs of diameter two
• On mixed Moore graphs

Cited in

(8)

• An improved upper bound for the order of mixed graphs
• On networks with order close to the Moore bound
• A new general family of mixed graphs
• Construction of extremal mixed graphs of diameter two
• scientific article; zbMATH DE number 3859160 (Why is no real title available?)
• Moore mixed graphs from Cayley graphs
• On large regular \(( 1 , 1 , k )\)-mixed graphs
• On bipartite (1,1,k)-mixed graphs

This page was built for publication: Sequence mixed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q505431)