The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph

Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f: V (G) → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f ₁, f ₂, …, f _d } of distinct Roman k-dominating functions on G with the property that Σ _i=1 ^d f _i (v) ≤ 2 for each v ∈ V (G), is called a Roman k-dominating family (of functions) on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by d _kR (G). Note that the Roman 1-domatic number d _1R (G) is the usual Roman domatic number d _R (G). In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for d _kR (G). In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.     

Bounds on the <Emphasis Type="Italic">k</Emphasis>-tuple domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A vertex of a graph G dominates itself and all vertices adjacent to it. A subset S ⊆ V (G) is a k-tuple dominating set of G if each vertex of V (G) is dominated by at least k vertices in S. The k-tuple domatic number of G is the largest number of sets in a partition of V (G) into k-tuple dominating sets.     

The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

On signed distance-k-domination in graphs

The signed distance-k-domination number of a graph is a certain variant of the signed domination number. If v is a vertex of a graph G, the open k-neighborhood of v, denoted by N _k (v), is the set N _k (v) = {u: u ≠ v and d(u, v) ⩽ k}. N _k [v] = N _k (v) ⋃ {v} is the closed k-neighborhood of v. A function f: V → {−1, 1} is a signed distance-k-dominating function of G, if for every vertex . The signed distance-k-domination number, denoted by γ _k,s (G), is the minimum weight of a signed distance-k-dominating function on G. The values of γ _2,s (G) are found for graphs with small diameter, paths, circuits. At the end it is proved that γ _2,s (T) is not bounded from below in general for any tree T.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

<Emphasis Type="Italic">f</Emphasis>-Colorings of some graphs of <Emphasis Type="Italic">f</Emphasis>-class 1

An f-coloring of a graph G is an edge-coloring of G such that each color appears at each vertex v V（G） at most f（v） times. The minimum number of colors needed to f-color G is called the f-chromatic index of G and is denoted by X′f（G）. Any simple graph G has the f-chromatic index equal to △f（G） or △f（G） ＋ 1, where △f（G） =max v V（G）{[d（v）/f（v）]}. If X′f（G） = △f（G）, then G is of f-class 1; otherwise G is of f-class 2. In this paper, a class of graphs of f-class 1 are obtained by a constructive proof. As a result, f-colorings of these graphs with △f（G） colors are given.     

（g, f）-Factorizations Randomly Orthogonal to a Subgraph in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued functions defined on V(G) such that 2k - 2 ≤g(x)≤f(x) for all x∈V(G). Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg m-1,mf-m 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.     

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

Vertex Set Partitions Preserving Conservativeness

Let G be an undirected graph and ={X₁, …, X_n} be a partition of V(G). Denote by G/ the graph which has vertex set {X₁, …, X_n}, edge set E, and is obtained from G by identifying vertices in each class X_i of the partition . Given a conservative graph (G, w), we study vertex set partitions preserving conservativeness, i.e., those for which (G/ , w) is also a conservative graph. We characterize the conservative graphs (G/ , w), where is a terminal partition of V(G) (a partition preserving conservativeness which is not a refinement of any other partition of this kind). We prove that many conservative graphs admit terminal partitions with some additional properties. The results obtained are then used in new unified short proofs for a co-NP characterization of Seymour graphs by A. A. Ageev, A. V. Kostochka, and Z. Szigeti (1997, J. Graph Theory34, 357–364), a theorem of E. Korach and M. Penn (1992, Math. Programming55, 183–191), a theorem of E. Korach (1994, J. Combin. Theory Ser. B62, 1–10), and a theorem of A. V. Kostochka (1994, in “Discrete Analysis and Operations Research. Mathematics and its Applications (A. D. Korshunov, Ed.), Vol. 355, pp. 109–123, Kluwer Academic, Dordrecht).     

Competitively Tight Graphs

The competition graph of a digraph D is a (simple undirected) graph which has the same vertex set as D and has an edge between two distinct vertices x and y if and only if there exists a vertex v in D such that (x, v) and (y, v) are arcs of D. For any graph G, G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number k(G) of a graph G is the smallest number of such isolated vertices. Computing the competition number of a graph is an NP-hard problem in general and has been one of the important research problems in the study of competition graphs. Opsut [1982] showed that the competition number of a graph G is related to the edge clique cover number θ _E (G) of the graph G via θ _E (G) ? |V(G)| + 2 ≤ k(G) ≤ θ _E (G). We first show that for any positive integer m satisfying 2 ≤ m ≤ |V(G)|, there exists a graph G with k(G) = θ _E (G) ? |V(G)| + m and characterize a graph G satisfying k(G) = θ _E (G). We then focus on what we call competitively tight graphs G which satisfy the lower bound, i.e., k(G) = θ _E (G) ? |V(G)| + 2. We completely characterize the competitively tight graphs having at most two triangles. In addition, we provide a new upper bound for the competition number of a graph from which we derive a sufficient condition and a necessary condition for a graph to be competitively tight.     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

Bounds on the Distance Two-Domination Number of a Graph

 For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ₂(G). In this note we obtain various upper bounds for γ₂(G) and characterize the classes of graphs attaining these bounds. Received: May 31, 1999 Final version received: July 13, 2000     

Inequalities involving independence domination, f-domination, connected and total f-domination numbers

Let f be an integer-valued function defined on the vertex set V(G) of a graph G. A subset D of V(G) is an f-dominating set if each vertex x outside D is adjacent to at least f(x) vertices in D. The minimum number of vertices in an f-dominating set is defined to be the f-domination number, denoted by _f (G). In a similar way one can define the connected and total f-domination numbers _c,f (G) and _t,f (G). If f(x) = 1 for all vertices x, then these are the ordinary domination number, connected domination number and total domination number of G, respectively. In this paper we prove some inequalities involving _f (G), _c,f (G), _t,f (G) and the independence domination number i(G). In particular, several known results are generalized.     

Degrees and choice numbers

The choice number ch(G) of a graph G=(V, E) is the minimum number k such that for every assignment of a list S(v) of at least k colors to each vertex v∈V, there is a proper vertex coloring of G assigning to each vertex v a color from its list S(v). We prove that if the minimum degree of G is d, then its choice number is at least (½−o(1))log₂ d, where the o(1)‐term tends to zero as d tends to infinity. This is tight up to a constant factor of 2+o(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 364–368, 2000     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

Inequalities for the first‐fit chromatic number

The First‐Fit (or Grundy) chromatic number of G, written as χ_FF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C₄‐free bipartite graphs with χ_FF(G) = k is asymptotically 2k² (the upper bound answers a problem of Zaker [9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008     

Spectral radius of digraphs with given dichromatic number

Let D be a digraph with vertex set V(D). A partition of V(D) into k acyclic sets is called a k-coloring of D. The minimum integer k for which there exists a k-coloring of D is the dichromatic number χ(D) of the digraph D. Denote G_n,k the set of the digraphs of order n with the dichromatic number k≥2. In this note, we characterize the digraph which has the maximal spectral radius in G_n,k. Our result generalizes the result of [8] by Feng et al.     

Two Paths Joining Given Vertices in 2k-Edge-Connected Graphs

Let k≥2 be an integer and G = (V(G), E(G)) be a k-edge-connected graph. For X⊆V(G), e(X) denotes the number of edges between X and V(G) − X. Let {s_i, t_i}⊆X_i⊆V(G) (i=1,2) and X₁∩X₂=∅. We here prove that if k is even and e(X_i)≤2k−1 (i=1,2), then there exist paths P₁ and P₂ such that P_i joins s_i and t_i, V(P_i)⊆X_i (i=1,2) and G − E(P₁∪P₂) is (k−2)-edge-connected (for odd k, if e(X₁)≤2k−2 and e(X₂)≤2k−1, then the same result holds [10]), and we give a generalization of this result and some other results about paths not containing given edges.     

On <Emphasis Type="Italic">k</Emphasis>-pairable graphs from trees

The concept of the k-pairable graphs was introduced by Zhibo Chen (On k-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p(G), called the pair length of a graph G, as the maximum k such that G is k-pairable and p(G) = 0 if G is not k-pairable for any positive integer k. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved are restricted to be trees. That is, we characterize the trees G with p(G) = 1 and prove that p(G □ H) = p(G) + p(H) when both G and H are trees.     

List Colorings of K5‐Minor‐Free Graphs With Special List Assignments

The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K₅‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[S_k], where S_k: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(S_k) in G between the components of G[S_k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012