The classification of complete graphsK n onf-coloring

Anf-coloring of a graphG=(V, E) is a coloring of edge setE such that each color appears at each vertexv ∈ V at mostf(v) times. The minimum number of colors needed tof-colorG is called thef-chromatic index χ′ _f (G) ofG. Any graphG hasf-chromatic index equal to Δ _f (G) or Δ _f (G) + 1 where $\Delta _f (G) = \mathop {\max }\limits_{v \in V} \left\{ {\left\lceil {\frac{{d(v)}}{{f(v)}}} \right\rceil } \right\}$ . If χ′ _f (G) = Δ _f (G), thenG is ofC _f 1; otherwiseG is ofC _f 2. In this paper, the classification problem of complete graphs onf-coloring is solved completely.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

A special f-edge cover-coloring of multigraphs

An edge cover-coloring of G is called a special (f,g)-edge cover-coloring, if each color appears at each vertex at least f(v) times and the number of multiple edges receive the same color is at most g(vw) for vw∈E(G). Let $\chi_{f_{g}}''$ denote the maximum positive integer k for which using k colors a special (f,g)-edge cover-coloring of G exists. The existence of $\chi_{f_{g}}''$ is discussed and the lower bound of $\chi_{f_{g}}''$ is obtained.     

Super edge-magic strength of fire crackers, banana trees and unicyclic graphs

A graph G(V,E) is called super edge-magic if there exists a bijection f from V∪E to {1,2,3,…,|V|+|E|} such that f(u)+f(v)+f(uv)=c(f) is constant for any uv∈E and f(V)={1,2,3,…,|V|}. Such a bijection is called a super edge-magic labeling of G. The super edge-magic strength of a graph G is defined as the minimum of all c(f) where the minimum runs over all super edge-magic labelings of G and is denoted by sm(G). The super edge-magic strength of some families of graphs are obtained in this paper.     

Fractional f-Edge Cover Chromatic Index of Graphs

Let G be a graph, and let f be an integer function on V with ${1\leq f(v)\leq d(v)}$ to each vertex ${\upsilon \in V}$ . An f-edge cover coloring is a coloring of edges of E(G) such that each color appears at each vertex ${\upsilon \in V(G)}$ at least f(υ) times. The maximum number of colors needed to f-edge cover color G is called the f-edge cover chromatic index of G and denoted by ${\chi^{'}_{fc}(G)}$ . It is well known that any simple graph G has the f-edge cover chromatic index equal to δ _f (G) or δ _f (G) ? 1, where ${\delta_{f}(G)=\,min\{\lfloor \frac{d(v)}{f(v)} \rfloor: v\in V(G)\}}$ . The fractional f-edge cover chromatic index of a graph G, denoted by ${\chi^{'}_{fcf}(G)}$ , is the fractional f-matching number of the edge f-edge cover hypergraph ${\mathcal{H}}$ of G whose vertices are the edges of G and whose hyperedges are the f-edge covers of G. In this paper, we give an exact formula of ${\chi^{'}_{fcf}(G)}$ for any graph G, that is, ${\chi^{'}_{fcf}(G)=\,min \{\min\limits_{v\in V(G)}d_{f}(v), \lambda_{f}(G)\}}$ , where ${\lambda_{f}(G)=\min\limits_{S} \frac{|C[S]|}{\lceil (\sum\limits_{v\in S}{f(v)})/2 \rceil}}$ and the minimum is taken over all nonempty subsets S of V(G) and C[S] is the set of edges that have at least one end in S.     

Signed k-independence in graphs

Let k ≥ 2 be an integer. A function f: V(G) → {?1, 1} defined on the vertex set V(G) of a graph G is a signed k-independence function if the sum of its function values over any closed neighborhood is at most k ? 1. That is, Σ _x∈N[v] f(x) ≤ k ? 1 for every v ∈ V(G), where N[v] consists of v and every vertex adjacent to v. The weight of a signed k-independence function f is w(f) = Σ _v∈V(G) f(v). The maximum weight w(f), taken over all signed k-independence functions f on G, is the signed k-independence number α _s ^k (G) of G. In this work, we mainly present upper bounds on α _s ^k (G), as for example α _s ^k (G) ≤ n ? 2?(Δ(G) + 2 ? k)/2?, and we prove the Nordhaus-Gaddum type inequality $\alpha _S^k \left( G \right) + \alpha _S^k \left( {\bar G} \right) \leqslant n + 2k - 3$ , where n is the order, Δ(G) the maximum degree and $\bar G$ the complement of the graph G. Some of our results imply well-known bounds on the signed 2-independence number.     

Roman domination subdivision number of graphs

A Roman dominating function on a graph G = (V, E) is a function f : V ? {0, 1, 2}f : V \rightarrow \{0, 1, 2\} satisfying the condition that every vertex v for which f(v) = 0 is adjacent to at least one vertex u for which f(u) = 2. The weight of a Roman dominating function is the value w(f) = ?_{v ? V} f(v)w(f) = \sum_{v\in V} f(v). The Roman domination number of a graph G, denoted by _gR(G)_{\gamma R}(G), equals the minimum weight of a Roman dominating function on G. The Roman domination subdivision number sd_gR(G)sd_{\gamma R}(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the Roman domination number. In this paper, first we establish upper bounds on the Roman domination subdivision number for arbitrary graphs in terms of vertex degree. Then we present several different conditions on G which are sufficient to imply that $1 \leq sd_{\gamma R}(G) \leq 3$1 \leq sd_{\gamma R}(G) \leq 3. Finally, we show that the Roman domination subdivision number of a graph can be arbitrarily large.     

On the Super Edge-Magic Deficiency of Graphs

A (p, q) graph G is edge-magic if there exists a bijective function f: V(G) ∪ E(G) → {1,2,…,p + q} such that f(u) + f(v) + f(uv) = k is a constant, called the valence of f, for any edge uv of G. Moreover, G is said to be super edge-magic if f(V(G)) = {1,2,…,p}. The question studied in this paper is for which graphs is it possible to add a finite number of isolated vertices so that the resulting graph is super edge-magic? If it is possible for a given graph G, then we say that the minimum such number of isolated vertices is the super edge-magic deficiency, μ_s(G) of G; otherwise we define it to be + ∞.     

On the adjacent vertex-distinguishing equitable edge coloring of graphs

Let G(V, E) be a graph. A k-adjacent vertex-distinguishing equatable edge coloring of G, k-AVEEC for short, is a proper edge coloring f if (1) C(u)≠C(v) for uv ∈ E(G), where C(u) = {f(uv)|uv ∈ E}, and (2) for any i, j = 1, 2,… k, we have ||Ei| |Ej|| ≤ 1, where Ei = {e|e ∈ E(G) and f(e) = i}. χáve (G) = min{k| there exists a k-AVEEC of G} is called the adjacent vertex-distinguishing equitable edge chromatic number of G. In this paper, we obtain the χáve (G) of some special graphs and present a conjecture.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

Cohen-Macaulay type of the face poset of a plane graph

How can we calculate the Cohen-Macaulay type of a Cohen-Macaulay poset? This paper is an extension of earlier results in [2]. We give an explicit formula for the Cohen-Macaulay type of the face poset of a plane graph. Let G be a finite connected plane graph allowing loops and multiple edges and G* the subgraph obtained by removing all loops from G. For each vertexv of G the number of connected components of G* —v is denoted by δ_G (v). Also, writev _G (v) for the number of loops of G incident tov. Then the Cohen-Macaulay type of the face poset of G is $\left[ {\sum\limits_\upsilon {2\left\{ {\delta _G (v) + v_G (v) - 1} \right\}} } \right] + 1$ .     

Adjacent strong edge coloring of graphs

For a graph G(V, E), if a proper k-edge coloring ƒ is satisfied with C(u) ≠ C(v) for uv ∈ E(G), where $\text{C(u) = {ƒ(uv) | uv ∈ E}}$, then ƒ is called k-adjacent strong edge coloring of G, is abbreviated k-ASEC, and χ′_as(G) = min{k | k-ASEC of G} is called the adjacent strong edge chromatic number of G. In this paper, we discuss some properties of χ′_as(G), and obtain the χ′_as(G) of some special graphs and present a conjecture: if G are graphs whose order of each component is at least six, then χ′_as(G) ≤ Δ(G) + 2, where Δ(G) is the maximum degree of G.     

A note on Roman domination in graphs

Let G=(V,E) be a simple graph. A subset S⊆V is a dominating set of G, if for any vertex u∈V-S, there exists a vertex v∈S such that uv∈E. The domination number of G, γ(G), equals the minimum cardinality of a dominating set. A Roman dominating function on graph G=(V,E) is a function f:V→{0,1,2} satisfying the condition that every vertex v for which f(v)=0 is adjacent to at least one vertex u for which f(u)=2. The weight of a Roman dominating function is the value f(V)=∑_v∈Vf(v). The Roman domination number of a graph G, denoted by γ_R(G), equals the minimum weight of a Roman dominating function on G. In this paper, for any integer k(2?k?γ(G)), we give a characterization of graphs for which γ_R(G)=γ(G)+k, which settles an open problem in [E.J. Cockayne, P.M. Dreyer Jr, S.M. Hedetniemi et al. On Roman domination in graphs, Discrete Math. 278 (2004) 11-22].     

On super edge-antimagic total labelings of

A graph G of order p and size q is called (a,d)-edge-antimagic total if there exists a bijective function f:V(G)E(G)→{1,2,…,p+q} such that the edge-weights w(uv)=f(u)+f(v)+f(uv), uvE(G), form an arithmetic sequence with first term a and common difference d. The graph G is said to be super (a,d)-edge-antimagic total if the vertex labels are 1,2,…,p. In this paper we study super (a,d)-edge-antimagic properties of mK_n, that is, of the graph formed by the disjoint union of m copies of K_n.     

The profile of the Cartesian product of graphs

Given a graph G, a proper labelingf of G is a one-to-one function from V(G) onto {1,2,…,|V(G)|}. For a proper labeling f of G, the profile widthw_f(v) of a vertex v is the minimum value of f(v)−f(x), where x belongs to the closed neighborhood of v. The profile of a proper labelingfofG, denoted by P_f(G), is the sum of all the w_f(v), where v∈V(G). The profile ofG is the minimum value of P_f(G), where f runs over all proper labeling of G. In this paper, we show that if the vertices of a graph G can be ordered to satisfy a special neighborhood property, then so can the graph G×Q_n. This can be used to determine the profile of Q_n and K_m×Q_n.     

The Number of Independent Sets in a Graph with Small Maximum Degree

Let ind(G) be the number of independent sets in a graph G. We show that if G has maximum degree at most 5 then

Lower negative decision number in a graph

Let G=(V,E) be a graph. A function f:V(G)→{?1,1} is called bad if ∑ _v∈N(v) f(v)≤1 for every v∈V(G). A bad function f of a graph G is maximal if there exists no bad function g such that g≠f and g(v)≥f(v) for every v∈V. The minimum of the values of ∑ _v∈V f(v), taken over all maximal bad functions f, is called the lower negative decision number and is denoted by β _D ^* (G). In this paper, we present sharp lower bounds on this number for regular graphs and nearly regular graphs, and we also characterize the graphs attaining those bounds.     

Some results on exclusive sum graphs

Let N(Z) denote the set of all positive integers (integers). The sum graph G ⁺(S) of a finite subset S?N(Z) is the graph (S,E) with uv∈E if and only if u+v∈S. A graph G is said to be an (integral) sum graph if it is isomorphic to the sum graph of some S?N(Z). A sum labelling S is called an exclusive sum labelling if u+v∈S?V(G) for any edge uv∈E(G). We say that G is labeled exclusively. The least number r of isolated vertices such that G∪rK ₁ is an exclusive sum graph is called the exclusive sum number ε(G) of graph G. In this paper, we discuss the exclusive sum number of disjoint union of two graphs and the exclusive sum number of some graph classes.     

On Integral Sum Graphs

A graph G is said to be an integral sum graph if its nodes can be given a labeling f with distinct integers, so that for any two distinct nodes u and v of G, uv is an edge of G if and only if f(u)+f(v) = f(w) for some node w in G. A node of G is called a saturated node if it is adjacent to every other node of G. We show that any integral sum graph which is not K₃ has at most two saturated nodes. We determine the structure for all integral sum graphs with exactly two saturated nodes, and give an upper bound for the number of edges of a connected integral sum graph with no saturated nodes. We introduce a method of identification on constructing new connected integral sum graphs from given integral sum graphs with a saturated node. Moreover, we show that every graph is an induced subgraph of a connected integral sum graph. Miscellaneous relative results are also presented.     

On the Roman Bondage Number of Planar Graphs

A Roman dominating function on a graph G is a function f : V(G) → {0, 1, 2} satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex v for which f (v) = 2. The weight of a Roman dominating function is the value f (V(G)) = ?_{u ? V(G)} f (u){f (V(G)) = \sum_{u\in V(G)} f (u)}. The Roman domination number, γ _R (G), of G is the minimum weight of a Roman dominating function on G. The Roman bondage number b _R (G) of a graph G with maximum degree at least two is the minimum cardinality of all sets E^￠ í E(G){E^{\prime} \subseteq E(G)} for which γ _R (G − E′) > γ _R (G). In this paper we present different bounds on the Roman bondage number of planar graphs.