Wyniki wyszukiwania - BazTech

1

Total connected domination game

Bujtas Csilla, Henning Michael A., Irsic Vesna, Klavzar Sandi

Opuscula Mathematica

|

2021

|

Vol. 41, no. 4

453--464

EN

The (total) connected domination game on a graph G is played by two players, Dominator and Staller, according to the standard (total) domination game with the additional requirement that at each stage of the game the selected vertices induce a connected subgraph of G. If Dominator starts the game and both players play optimally, then the number of vertices selected during the game is the (total) connected game domination number [formulas] of G. We show that [formulas], and consequently define G as Class i if [formula] for i ∈ {0, 1, 2}. A large family of Class 0 graphs is constructed which contains all connected Cartesian product graphs and connected direct product graphs with minimum degree at least 2. We show that no tree is Class 2 and characterize Class 1 trees. We provide an infinite family of Class 2 bipartite graphs.

2

Wiener index of strong product of graphs

Peterin I., Zigert-Pletersek P.

Opuscula Mathematica

|

2018

|

Vol. 38, no. 1

81--94

EN

The Wiener index of a connected graph G is the sum of distances between all pairs of vertices of G. The strong product is one of the four most investigated graph products. In this paper the general formula for the Wiener index of the strong product of connected graphs is given. The formula can be simplified if both factors are graphs with the constant eccentricity. Consequently, closed formulas for the Wiener index of the strong product of a connected graph G of constant eccentricity with a cycle are derived.

3

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.

4

Equitable coloring of graph products

Furmańczyk H.

Opuscula Mathematica

|

2006

|

Vol. 26, no. 1

31-44

EN

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the "equitable chromatic number" of G and denoted by χ=(G). It is interesting to note that if a graph G is equitably k-colorable, it does not imply that it is equitably (k + 1)-colorable. The smallest integer k for which G is equitably k'-colorable for all k' ≥ k is called "the equitable chromatic threshold" of G and denoted by χ*=(G). In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [2] for Cartesian, weak and strong tensor products.