Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cubic graph

Sortuj według:

Ogranicz wyniki do:

On 2-rainbow domination number of functigraph and its complement

Shaminezhad Athena, Vatandoost Ebrahim

Opuscula Mathematica

2020

Vol. 40, no. 5

617--627

Let G be a graph and ƒ : V(G) → P({1, 2}) be a function where for every vertex v ∈ V(G), with ƒ (v) = ∅ we have [formula]. Then ƒ is a 2-rainbow dominating function or a 2RDF of G. The weight of ƒ is[formula]. The minimum weight of all 2-rainbow dominating functions is 2-rainbow domination number of G, denoted by [formula]. Let G 1 and G2 be two copies of a graph G with disjoint vertex sets V(G 1) and V(G2), and let σ be a function from V(G 1) to V(G2). We define the functigraph C(G,σ) to be the graph that has the vertex set V(C(G, ,σ)) = V(G 1) U V(G2), and the edge set [formula]. In this paper, 2-rainbow domination number of the functigraph of C(G, ,σ) and its complement are investigated. We obtain a general bound for [formula] and we show that this bound is sharp.

Equitable and semi-equitable coloring of cubic graphs and its application in batch scheduling

Furmańczyk H., Kubale M.

Archives of Control Sciences

2015

Vol. 25, no. 1

109--116

In the paper we consider the problems of equitable and semi-equitable coloring of vertices of cubic graphs. We show that in contrast to the equitable coloring, which is easy, the problem of semi-equitable coloring is NP-complete within a broad spectrum of graph parameters. This affects the complexity of batch scheduling of unit-length jobs with cubic incompatibility graph on three uniform processors to minimize the makespan.

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

Formanowicz P., Tanaś K.

International Journal of Applied Mathematics and Computer Science

2012

Vol. 22, no. 3

765-778

It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.