Wyniki wyszukiwania - BazTech

1

On b-vertex and b-edge critical graphs

Eschouf N. I., Blidia M.

Opuscula Mathematica

|

2015

|

Vol. 35, no. 2

171--180

EN

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number b(G) of a graph G is the largest integer k such that G admits a b-coloring with k colors. A simple graph G is called b+-vertex (edge) critical if the removal of any vertex (edge) of G increases its b-chromatic number. In this note, we explain some properties in b+-vertex (edge) critical graphs, and we conclude with two open problems.

2

Dynamic Coloring of Graphs

Borowiecki P., Sidorowicz E.

Fundamenta Informaticae

|

2012

|

Vol. 114, nr 2

105-128

EN

Dynamics is an inherent feature of many real life systems so it is natural to define and investigate the properties of models that reflect their dynamic nature. Dynamic graph colorings can be naturally applied in system modeling, e.g. for scheduling threads of parallel programs, time sharing in wireless networks, session scheduling in high-speed LAN’s, channel assignment inWDM optical networks as well as traffic scheduling. In the dynamic setting of the problem, a graph we color is not given in advance and new vertices together with adjacent edges are revealed one after another at algorithm’s input during the coloring process. Moreover, independently of the algorithm, some vertices may lose their colors and the algorithm may be asked to color them again. We formally define a dynamic graph coloring problem, the dynamic chromatic number and prove various bounds on its value. We also analyze the effectiveness of the dynamic coloring algorithm Dynamic-Fit for selected classes of graphs. In particular, we deal with trees, products of graphs and classes of graphs for which Dynamic-Fit is competitive. Motivated by applications, we state the problemof dynamic coloringwith discoloring constraints for which the performance of the dynamic algorithmTime-Fit is analyzed and give a characterization of graphs k-critical for Time-Fit. Since for any fixed k > 0 the number of such graphs is finite, it is possible to decide in polynomial time whether Time-Fit will always color a given graph with at most k colors.

3

Weakly connected domination critical graphs

Lemańska M., Patyk A.

Opuscula Mathematica

|

2008

|

Vol. 28, no. 3

325-330

EN

A dominating set D ⊂ V(G) is a weakly connected dominating set in G if the subgraph G[D]w = (NG[D], Ew) weakly induced by D is connected, where Ew is the set of all edges with at least one vertex in D. The weakly connected domination number ϒw(G) of a graph G is the minimum cardinality among all weakly connected dominating sets in G. The graph is said to be weakly connected domination critical (ϒw-critical) if for each u, v ∈ V(G) with v not adjacent to u, ϒw(G + vu) < ϒw(G). Further, G is k- ϒw-critical if ϒw(G) = k and for each edge e ∉ E(G), ϒw(G + e) < k. In this paper we consider weakly connected domination critical graphs and give some properties of 3-ϒw,-critical graphs.