On Schreier graphs of gyrogroup actions

The notion of a group action can be extended to the case of gyrogroups. In this article, we examine a digraph and graph associated with a gyrogroup action on a finite nonempty set, called a Schreier digraph and graph. We show that algebraic properties of gyrogroups and gyrogroup actions such as being gyrocommutative, being transitive, and being fixed-point-free are reflected in their Schreier digraphs and graphs. We also prove graph-theoretic versions of the three fundamental theorems involving actions: the Cauchy–Frobenius lemma (also known as the Burnside lemma), the orbit-stabilizer theorem, and the orbit decomposition theorem. Finally, we make a connection between gyrogroup actions and actions of symmetric groups by evaluation via Schreier digraphs and graphs.     

Reinforcement numbers of digraphs

The reinforcement number of a graph G is the minimum cardinality of a set of extra edges whose addition results in a graph with domination number less than the domination number of G. In this paper we consider this parameter for digraphs, investigate the relationship between reinforcement numbers of undirected graphs and digraphs, and obtain further results for regular graphs. We also determine the exact values of the reinforcement numbers of de Bruijn digraphs and Kautz digraphs.     

Infinite,highly connected digraphs with no two arc-disjoint spanning trees

We present a construction of countably infinite, highly connected graphs and digraphs, which shows that several basic connectivity results on finite graphs, including Edmondsapos;s branching theorem, cannot be extended to the infinite case.     

s-homotopy for finite graphs

We introduce the notion of “s-dismantlability” which will give in the category of finite graphs an analogue of formal deformations defining the simple-homotopy type in the category of finite simplicial complexes. More precisely, s-dismantlability allows us to define an equivalence relation whose equivalence classes are called “s-homotopy types” and we get a correspondence between s-homotopy types in the category of graphs and simple-homotopy types in the category of simplicial complexes by the way of classical functors between these two categories (theorem 3.6). Next, we relate these results to similar results obtained by Barmak and Minian (2006) within the framework of posets (theorem 4.2).     

On extremal weighted digraphs with no heavy paths

Bollobás and Scott proved that if the weighted outdegree of every vertex of an edge-weighted digraph is at least 1, then the digraph contains a (directed) path of weight at least 1. In this note we characterize the extremal weighted digraphs with no heavy paths. Our result extends a corresponding theorem of Bondy and Fan on weighted graphs. We also give examples to show that a result of Bondy and Fan on the existence of heavy paths connecting two given vertices in a 2-connected weighted graph does not extend to 2-connected weighted digraphs.     

On the structure of locally semicomplete digraphs

In this paper we continue the study, started by J. Bang-Jensen (1989), of locally semicomplete digraphs, a generalization of tournaments, to which many well-known tournament results extend. The underlying undirected graphs of the locally semicomplete digraphs are precisely the proper circular-arc graphs. We give new results on the structure of locally semicomplete digraphs, as well as several examples of properties of tournaments and semicomplete digraphs that do not extend to the class of locally semicomplete digraphs.     

An Eulerian exposition

An overview of Eulerian graphs is presented. In particular, characterizations of Eulerian graphs and digraphs as well as algorithms for constructing Eulerian circuits are discussed. A solution to the Chinese postman problem is followed by a study of subgraphs and supergraphs of Eulerian graphs. After an introduction to randomly Eulerian graphs and digraphs, we conclude with a summary of a variety of results involving enumeration.     

Geometric partial comodules over flat coalgebras in Abelian categories are globalizable

The aim of this paper is to prove the statement in the title. As a by-product, we obtain new globalization results in cases never considered before, such as partial corepresentations of Hopf algebras. Moreover, we show that for partial representations of groups and Hopf algebras, our globalization coincides with those described earlier in literature. Finally, we introduce Hopf partial comodules over a bialgebra as geometric partial comodules in the monoidal category of (global) modules. By applying our globalization theorem we obtain an analogue of the fundamental theorem for Hopf modules in this partial setting.     

Chip-firing based methods in the Riemann–Roch theory of directed graphs

Baker and Norine proved a Riemann–Roch theorem for divisors on undirected graphs. The notions of graph divisor theory are in duality with the notions of the chip-firing game of Björner, Lovász and Shor. We use this connection to prove Riemann–Roch-type results on directed graphs. We give a simple proof for a Riemann–Roch inequality on Eulerian directed graphs, improving a result of Amini and Manjunath. We also study possibilities and impossibilities of Riemann–Roch-type equalities in strongly connected digraphs and give examples. We intend to make the connections of this theory to graph theoretic notions more explicit via using the chip-firing framework.     

Characterizing Extremal Digraphs for Identifying Codes and Extremal Cases of Bondy’s Theorem on Induced Subsets

An identifying code of a (di)graph G is a dominating subset C of the vertices of G such that all distinct vertices of G have distinct (in)neighbourhoods within C. In this paper, we classify all finite digraphs which only admit their whole vertex set as an identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well-known theorem of Bondy on set systems, we classify the extremal cases for this theorem.     

Spectral criterion for cycle balance in networks

A network is cycle balanced if the product of the weights (nonzero real numbers) of the lines of every cycle in it is positive. In this paper, we prove that a network D is cycle balanced if and only if its adjacency matrix is isospectral with its nonnegative counterpart. Consequent to this theorem is an analogous criterion for structural balance in sigraphs (abbreviation for “signed graphs”) as also for cycle balance in signed digraphs. These criteria establish in a natural way a wide scope for cospectrality considerations in the classes of signed digraphs and sigraphs.     

Locally semicomplete digraphs: A generalization of tournaments

In this paper we introduce a new class of directed graphs called locally semicomplete digraphs. These are defined to be those digraphs for which the following holds: for every vertex x the vertices dominated by x induce a semicomplete digraph and the vertices that dominate x induce a semicomplete digraph. (A digraph is semicomplete if for any two distinct vertices u and ν, there is at least one arc between them.) This class contains the class of semicomplete digraphs, but is much more general. In fact, the class of underlying graphs of the locally semi-complete digraphs is precisely the class of proper circular-arc graphs (see [13], Theorem 3). We show that many of the classic theorems for tournaments have natural analogues for locally semicomplete digraphs. For example, every locally semicomplete digraph has a directed Hamiltonian path and every strong locally semicomplete digraph has a Hamiltonian cycle. We also consider connectivity properties, domination orientability, and algorithmic aspects of locally semicomplete digraphs. Some of the results on connectivity are new, even when restricted to semicomplete digraphs.     

Characterization of n-path graphs and of graphs having nth root

We characterize connected graphs and digraphs having an nth root and so generalize results by A. Mukhopadhyay and D. P. Geller, respectively. We then define the n-path graph of a graph and characterize those graphs which are n-path graphs. This extends recent results by B. Devadas Acharya and M. N. Vartak. The corresponding problem for digraphs is also considered.     

Locally-finite connected-homogeneous digraphs

A digraph is connected-homogeneous if any isomorphism between finite connected induced subdigraphs extends to an automorphism of the digraph. We consider locally-finite connected-homogeneous digraphs with more than one end. In the case that the digraph embeds a triangle we give a complete classification, obtaining a family of tree-like graphs constructed by gluing together directed triangles. In the triangle-free case we show that these digraphs are highly arc-transitive. We give a classification in the two-ended case, showing that all examples arise from a simple construction given by gluing along a directed line copies of some fixed finite directed complete bipartite graph. When the digraph has infinitely many ends we show that the descendants of a vertex form a tree, and the reachability graph (which is one of the basic building blocks of the digraph) is one of: an even cycle, a complete bipartite graph, the complement of a perfect matching, or an infinite semiregular tree. We give examples showing that each of these possibilities is realised as the reachability graph of some connected-homogeneous digraph, and in the process we obtain a new family of highly arc-transitive digraphs without property Z.     

Efficient total domination in digraphs

We generalize the concept of efficient total domination from graphs to digraphs. An efficiently total dominating set X of a digraph D is a vertex subset such that every vertex of D has exactly one predecessor in X. We study graphs that permit an orientation having such a set and give complexity results and characterizations. Furthermore, we study the computational complexity of the (weighted) efficient total domination problem for several digraph classes. In particular we deal with most of the common generalizations of tournaments, like locally semicomplete and arc-locally semicomplete digraphs.     

On well quasi-order of graph classes under homomorphic image orderings

In this paper we consider the question of well quasi-order for classes defined by a single obstruction within the classes of all graphs, digraphs and tournaments, under the homomorphic image ordering (in both its standard and strong forms). The homomorphic image ordering was introduced by the authors in a previous paper and corresponds to the existence of a surjective homomorphism between two structures. We obtain complete characterisations in all cases except for graphs under the strong ordering, where some open questions remain.     

Arc transitive covering digraphs and their eigenvalues

We prove that every finite regular digraph has an arc-transitive covering digraph (whose arcs are equivalent under automorphisms) and every finite regular graph has a 2-arc-transitive covering graph. As a corollary, we sharpen C. D. Godsil's results on eigenvalues and minimum polynomials of vertex-transitive graphs and digraphs. Using Godsil's results, we prove, that given an integral matrix A there exists an arc-transitive digraph X such that the minimum polynomial of A divides that of X. It follows that there exist arc-transitive digraphs with nondiagonalizable adjacency matrices, answering a problem by P. J. Cameron. For symmetric matrices A, we construct a 2-arc-transitive graphs X.     

Further mathematical properties of Cayley digraphs applied to hexagonal and honeycomb meshes

In this paper, we extend known relationships between Cayley digraphs and their subgraphs and coset graphs with respect to subgroups to obtain a number of general results on homomorphism between them. Intuitively, our results correspond to synthesizing alternative, more economical, interconnection networks by reducing the number of dimensions and/or link density of existing networks via mapping and pruning. We discuss applications of these results to well-known and useful interconnection networks such as hexagonal and honeycomb meshes, including the derivation of provably correct shortest-path routing algorithms for such networks.     

An inequality for the group chromatic number of a graph

We give an inequality for the group chromatic number of a graph as an extension of Brooks’ Theorem. Moreover, we obtain a structural theorem for graphs satisfying the equality and discuss applications of the theorem.     

Orthoscalar quiver representations corresponding to extended Dynkin graphs in the category of Hilbert spaces

It is known that finitely representable quivers correspond to Dynkin graphs and tame quivers correspond to extended Dynkin graphs. In an earlier paper, the authors generalized some of these results to locally scalar (later renamed to orthoscalar) quiver representations in Hilbert spaces; in particular, an analog of the Gabriel theorem was proved. In this paper, we study the relationships between indecomposable representations in the category of orthoscalar representations and indecomposable representations in the category of all quiver representations. For the quivers corresponding to extended Dynkin graphs, the indecomposable orthoscalar representations are classified up to unitary equivalence.