Wyniki wyszukiwania - BazTech

1

On minimum intersections of certain secondary dominating sets in graphs

Kosiorowska Anna, Michalski Adrian, Włoch Iwona

Opuscula Mathematica

|

2023

|

Vol. 43, no. 6

813--827

EN

In this paper we consider secondary dominating sets, also named as (1,k)-dominating sets, introduced by Hedetniemi et al. in 2008. In particular, we study intersections of the (1, 1)-dominating sets and proper (1, 2)-dominating sets. We introduce (1,2)-intersection index as the minimum possible cardinality of such intersection and determine its value for some classes of graphs.

2

M2-edge colorings of dense graphs

Ivanco J.

Opuscula Mathematica

|

2016

|

Vol. 36, no. 5

603–-612

EN

An edge coloring φ of a graph G is called an Mi-edge coloring if [formula] every vertex v of G, where φ (v) is the set of colors of edges incident with v. Let K1(G) denote the maximum number of colors used in an Mi-edge coloring of G. In this paper we establish some bounds of K.2(G), present some graphs achieving the bounds and determine exact values of K.2(G) for dense graphs.

3

Generation of cyber-security reinforcement strategies for smart grid based on the attribute-based attack graph

Zhang B., Li Q., Zhang Y., Liu X., Ni Z.

Journal of Power Technologies

|

2016

|

Vol. 96, nr 3

170--177

EN

A smart grid is a kind of energy cyber-physical system (ECPS) with the interdependency of information and physicality. A cyber-attack gravely threatens the safe and stable operation of a physical power grid. Cyber-security reinforcement of smart grid has become a research issue. However, the information network scale of a smart grid is massive, and the generation of security reinforcement strategies has become a problem. Therefore, a generation method of security reinforcement strategies based on an attribute-based attack graph was proposed in this study. The method defined a smart grid based on premise and consequence attributes to form an attribute-based attack graph. With this graph, the method for the generation of security reinforcement strategies was transferred to the minimum dominating set of the attribute-based attack graph and solved to realize space reduction in the security reinforcement strategies. An algorithm for the generation of security reinforcement strategies was designed based on the greedy algorithm, and strategies for large-scale cyber security reinforcement of the smart grid were determined to eliminate the complexity and difficulty of this problem effectively. Through a simulation analysis of a large-scale node network, the efficiency of the generation method of reinforcement strategies based on the attribute based attack graph and minimum dominating set was verified. Results show that the proposed method can be used for security reinforcement of large-scale complicated networks of a smart grid.

4

Domination hypergraphs of certain digraphs

Sonntag M., Teichert H. M.

Opuscula Mathematica

|

2010

|

Vol. 30, no. 2

179-191

EN

If D = (V,A) is a digraph, its domination hypergraph DH(D) = (V, E) has the vertex set V and e ⊆ V is an edge of DH(D) if and only if e is a minimal dominating set of D. We investigate domination hypergraphs of special classes of digraphs, namely tournaments, paths and cycles. Finally, using a special decomposition/composition method we construct edge sets of domination hypergraphs of certain digraphs.

5

Dominating sets and domination polynomials of certain graphs, II

Alikhani S., Yee-hock P.

Opuscula Mathematica

|

2010

|

Vol. 30, no. 1

37-51

EN

The domination polynomial of a graph G of order n is the polynomial [formula] where d(G, i) is the number of dominating sets of G of size i, and ϒ (G) is the domination number of G. In this paper, we obtain some properties of the coefficients of D(G, x). Also, by study of the dominating sets and the domination polynomials of specific graphs denoted by G'(m), we obtain a relationship between the domination polynomial of graphs containing an induced path of length at least three, and the domination polynomial of related graphs obtained by replacing the path by shorter path. As examples of graphs G' (m), we study the dominating sets and domination polynomials of cycles and generalized theta graphs. Finally, we show that, if n ≡ 0, 2(mod 3) and D(G, x) = D(Cn, x), then G = Cn.

6

On equality in an upper bound for the acyclic domination number

Samodivkin V.

Opuscula Mathematica

|

2008

|

Vol. 28, no. 3

331-334

EN

A subset A of vertices in a graph G is acyclic if the subgraph it induces contains no cycles. The acyclic domination number ϒa (G) of a graph G is the minimum cardinality of an acyclic dominating set of G. For any graph G with n vertices and maximum degree Δ(G), ϒa(G) ≤ n - Δ(G). In this paper we characterize the connected graphs and the connected triangle-free graphs which achieve this upper bound.

7

Weakly convex and convex domination numbers

Lemańska M.

Opuscula Mathematica

|

2004

|

Vol. 24, no. 2

181-188

EN

Two new domination parameters for a connected graph G: the weakly convex domination number of G and the convex domination number of G are introduced. Relations between these parameters and the other domination parameters are derived. In particular, we study for which cubic graphs the convex domination number equals the connected domination number.

8

NP-completeness of weakly convex and convex dominating set decision problems

Raczek J.

Opuscula Mathematica

|

2004

|

Vol. 24, no. 2

189-196

EN

The convex domination number and the weakly convex domination number are new domination parameters. In this paper we show that the decision problems of convex and weakly convex dominating sets are NP-complete for bipartite and split graphs. Using a modified version of Warshall algorithm we can verify in polynomial time whether a given subset of vertices of a graph is convex or weakly convex.