Results 41 to 50 of about 6,654 (223)
From Subkautz Digraphs to Cyclic Kautz Digraphs [PDF]
Journal of Interconnection Networks, 2018 The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed.
openaire +3 more sources
Some Results on 4-Transitive Digraphs
Discussiones Mathematicae Graph Theory, 2017 Let D be a digraph with set of vertices V and set of arcs A. We say that D is k-transitive if for every pair of vertices u, v ∈ V, the existence of a uv-path of length k in D implies that (u, v) ∈ A.
García-Vázquez Patricio Ricardo +1 more
doaj +1 more source
Graph partitioning: an updated survey
AKCE International Journal of Graphs and Combinatorics, 2023 Graph partitioning problem, which is one of the most important topics in graph theory, usually asks for a partition of the vertex set of a graph into pairwise disjoint subsets with various requirements. It comes from the well-known Max-Cut Problem: Given
Shufei Wu, Jianfeng Hou
doaj +1 more source
, 2023 In this work, we generalize several results on graph recolouring to digraphs. Given two k-dicolourings of a digraph D, we prove that it is PSPACE-complete to decide whether we can transform one into the other by recolouring one vertex at each step while ...
Picasarri-Arrieta, Lucas +4 more
core +6 more sources
Toward Wojda's conjecture on digraph packing [PDF]
Opuscula Mathematica, 2017 Given a positive integer \(m\leq n/2\), Wojda conjectured in 1985 that if \(D_1\) and \(D_2\) are digraphs of order \(n\) such that \(|A(D_1)|\leq n-m\) and \(|A(D_2)|\leq 2n-\lfloor n/m\rfloor-1\) then \(D_1\) and \(D_2\) pack.
Jerzy Konarski, Andrzej Żak
doaj +1 more source
When a digraph and its line digraph are connected and cospectral [PDF]
, 1998 In this paper we characterize all digraphs each one of which is cospectral with its line digraph and both the digraph and its line digraph are connected. Some related enumeration problems are also considered.
Lin, Guoning, Zhang, Fuji
core +3 more sources
H-kernels by walks in H-colored digraphs and the color-class digraph
AKCE International Journal of Graphs and Combinatorics, 2016 Let H be a digraph possibly with loops and D a finite digraph without loops whose arcs are colored with the vertices of H (D is an H-colored digraph). V(D) and A(D) will denote the sets of vertices and arcs of D respectively.
Hortensia Galeana-Sánchez +1 more
doaj +1 more source
Discrete Mathematics, 2014 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Yanmei Hong, Hong-Jian Lai, Qinghai Liu
openaire +1 more source
Exact and Approximate Digraph Bandwidth [PDF]
, 2019 In this paper, we introduce a directed variant of the classical Bandwidth problem and study it from the view-point of moderately exponential time algorithms, both exactly and approximately.
Jain, Pallavi +4 more
core +1 more source
On structural controllability in complex networks with periodic switching topologies
Asian Journal of Control, EarlyView.Abstract This paper investigates the structural controllability of complex networks with periodic switching topologies. First, several graph transformations that preserve structural controllability are demonstrated. Based on the n‐walk theory, a criterion is derived that determines structural controllability by analyzing only the joint graph within a ...
Jingrui Hou +3 more
wiley +1 more source