For a graphical property P and a graph G, a subset S of vertices of G is a P-set if the subgraph induced by S has the property P. The domination number with respect to the property P, denoted by γP (G), is the minimum cardinality of a dominating P-set. We define the domination multisubdivision number with respect to P, denoted by msdP (G), as a minimum positive integer k such that there exists an edge which must be subdivided k times to change γP (G). In this paper (a) we present necessary and sufficient conditions for a change of γP (G) after subdividing an edge of G once, (b) we prove that if e is an edge of a graph G then γP (Ge,1) < γP (G) if and only if γP (G − e) < γP (G) (Ge,t denotes the graph obtained from G by subdivision of e with t vertices), (c) we also prove that for every edge of a graph G we have γP (G − e) 6 γP (Ge,3) ≤ γP (G − e) + 1, and (d) we show that msdP (G) 6 3, where P is hereditary and closed under union with K1.
For a graphical property P and a graph G, a subset S of vertices of G is a P-set if the subgraph induced by S has the property P. The domination number with respect to the property P, is the minimum cardinality of a dominating P-set. In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate and hereditary properties when a graph is modified by adding an edge or deleting a vertex.
In this paper we present results on changing and unchanging of the domination number with respect to the nondegenerate property P, denoted by γP (G), when a graph G is modified by deleting a vertex or deleting edges. A graph G is (γP (G), k)P -critical if γP (G − S) < γP (G) for any set S ( V (G) with |S| = k. Properties of (γP , k)P -critical graphs are studied. The plus bondage number with respect to the property P, denoted b + P (G), is the cardinality of the smallest set of edges U ⊆ E(G) such that γP (G − U) > γP (G). Some known results for ordinary domination and bondage numbers are extended to γP (G) and b + P (G). Conjectures concerning b + P (G) are posed.
Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph G, a hereditary graph property P and l\geqslant 1 we define X{'_{P,l}} to be the minimum number of colours needed to properly colour the edges of G, such that any subgraph of G induced by edges coloured by (at most) l colours is in P. We present a necessary and sufficient condition for the existence of X{'_{P,l}} . We focus on edge-colourings of graphs with respect to the hereditary properties Ok and Sk, where Ok contains all graphs whose components have order at most k+1, and Sk contains all graphs of maximum degree at most k. We determine the value of X{'_{{S_k},l}}(G) for any graph G,k \geqslant 1, l\geqslant 1 and we present a number of results on X{'_{{O_k},l}}(G) ., Samantha Dorfling, Tomáš Vetrík., and Obsahuje seznam literatury