A Sokoban-type game and arc deletion within irregular digraphs of all sizes

2007

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…

Games without repetitions on graphs with vertex disjoint cycles

1997

Games without repetitions on graphs with vertex disjoint cycles are considered. We show that the problem finding of the game partition in this class reduces to this problem for trees. A method of finding of the game partition for trees have been given in [2].

Extremum degree sets of irregular oriented graphs and pseudodigraphs

2006