Search results for "05c20"
showing 2 items of 2 documents
Extremal Irregular Digraphs
2018
A digraph is called irregular if its distinct vertices have distinct degree pairs. An irregular digraph is called minimal (maximal) if the removal of any arc (addition of any new arc) results in a non-irregular digraph. It is easily seen that the minimum sizes among irregular n-vertex whether digraphs or oriented graphs are the same and are asymptotic to (√2/3) n3/2; maximum sizes, however, are asymptotic to n2 and n2/2, respectively. Let s stand for the sum of initial positive integers, s = 1, 3, 6, . . . . An oriented graph Hs and a digraph Fs, both large (in terms of the size), minimal irregular, and on any such s vertices, s ≥ 21, are constructed in [Large minimal irregular digraphs, Op…
THE HOMOLOGY OF DIGRAPHS AS A GENERALIZATION OF HOCHSCHILD HOMOLOGY
2010
J. Przytycki has established a connection between the Hochschild homology of an algebra $A$ and the chromatic graph homology of a polygon graph with coefficients in $A$. In general the chromatic graph homology is not defined in the case where the coefficient ring is a non-commutative algebra. In this paper we define a new homology theory for directed graphs which takes coefficients in an arbitrary $A-A$ bimodule, for $A$ possibly non-commutative, which on polygons agrees with Hochschild homology through a range of dimensions.