All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Page 1

Displaying 1 – 14 of 14

Showing per page

Nearly complete graphs decomposable into large induced matchings and their applications

Noga Alon, Ankur Moitra, Benjamin Sudakov (2013)

Journal of the European Mathematical Society

We describe two constructions of (very) dense graphs which are edge disjoint unions of large induced matchings. The first construction exhibits graphs on N vertices with ( N 2 ) - o ( N 2 ) edges, which can be decomposed into pairwise disjoint induced matchings, each of size N 1 - o ( 1 ) . The second construction provides a covering of all edges of the complete graph K N by two graphs, each being the edge disjoint union of at most N 2 - δ induced matchings, where δ > 0 , 076 . This disproves (in a strong form) a conjecture of Meshulam, substantially...

New results about impartial solitaire clobber

Eric Duchêne, Sylvain Gravier, Julien Moncel (2009)

RAIRO - Operations Research

Impartial Solitaire Clobber is a one-player version of the combinatorial game Clobber, introduced by Albert et al. in 2002. The initial configuration of Impartial Solitaire Clobber is a graph, such that there is a stone placed on each of its vertex, each stone being black or white. A move of the game consists in picking a stone, and clobbering an adjacent stone of the opposite color. By clobbering we mean that the clobbered stone is removed from the graph, and replaced by the clobbering one....

Currently displaying 1 – 14 of 14

Page 1