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

Previous Page 69 Next

Displaying 1361 – 1380 of 5365

Showing per page

Dichromatic number, circulant tournaments and Zykov sums of digraphs

Víctor Neumann-Lara (2000)

Discussiones Mathematicae Graph Theory

The dichromatic number dc(D) of a digraph D is the smallest number of colours needed to colour the vertices of D so that no monochromatic directed cycle is created. In this paper the problem of computing the dichromatic number of a Zykov-sum of digraphs over a digraph D is reduced to that of computing a multicovering number of an hypergraph H₁(D) associated to D in a natural way. This result allows us to construct an infinite family of pairwise non isomorphic vertex-critical k-dichromatic circulant...

Difference labelling of cacti

Martin Sonntag (2003)

Discussiones Mathematicae Graph Theory

A graph G is a difference graph iff there exists S ⊂ IN⁺ such that G is isomorphic to the graph DG(S) = (V,E), where V = S and E = i,j:i,j ∈ V ∧ |i-j| ∈ V. It is known that trees, cycles, complete graphs, the complete bipartite graphs K n , n and K n , n - 1 , pyramids and n-sided prisms (n ≥ 4) are difference graphs (cf. [4]). Giving a special labelling algorithm, we prove that cacti with a girth of at least 6 are difference graphs, too.

Difference labelling of digraphs

Martin Sonntag (2004)

Discussiones Mathematicae Graph Theory

A digraph G is a difference digraph iff there exists an S ⊂ N⁺ such that G is isomorphic to the digraph DD(S) = (V,A), where V = S and A = {(i,j):i,j ∈ V ∧ i-j ∈ V}.For some classes of digraphs, e.g. alternating trees, oriented cycles, tournaments etc., it is known, under which conditions these digraphs are difference digraphs (cf. [5]). We generalize the so-called source-join (a construction principle to obtain a new difference digraph from two given ones (cf. [5])) and construct a difference labelling...

Digraphs are 2-weight choosable.

Khatirinejad, Mahdad, Naserasr, Reza, Newman, Mike, Seamone, Ben, Stevens, Brett (2011)

The Electronic Journal of Combinatorics [electronic only]

Digraphs contractible onto * K 3

Stefan Janaqi, François Lescure, M. Maamoun, Henry Meyniel (1998)

Mathematica Bohemica

We show that any digraph on n ≥ 3 vertices and with not less than 3 n - 3 arcs is contractible onto * K 3 .

Digraphs with isomorphic underlying and domination graphs: connected U G c ( d )

Kim A.S. Factor, Larry J. Langley (2007)

Discussiones Mathematicae Graph Theory

The domination graph of a directed graph has an edge between vertices x and y provided either (x,z) or (y,z) is an arc for every vertex z distinct from x and y. We consider directed graphs D for which the domination graph of D is isomorphic to the underlying graph of D. We demonstrate that the complement of the underlying graph must have k connected components isomorphic to complete graphs, paths, or cycles. A complete characterization of directed graphs where k = 1 is presented.

Currently displaying 1361 – 1380 of 5365