The Decomposition Dimension of Graphs

 For an ordered k-decomposition ? = {G ₁, G ₂,…,G _k } of a connected graph G and an edge e of G, the ?-representation of e is the k-tuple r(e|?) = (d(e, G ₁), d(e, G ₂),…,d(e, G _k )), where d(e, G _i ) is the distance from e to G _i . A decomposition ? is resolving if every two distinct edges of G have distinct representations. The minimum k for which G has a resolving k-decomposition is its decomposition dimension dec(G). It is shown that for every two positive integers k and n≥ 2, there exists a tree T of order n with dec(T) = k. It is also shown that dec(G) ≤n for every graph G of order n≥ 3 and that dec(K _n ) ≤⌊(2n + 5)/3⌋ for n≥ 3. Received: June 17, 1998 Final version received: August 10, 1999     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Multiple recurrence and nilsequences

Aiming at a simultaneous extension of Khintchine(X,X,m,T)(X,\mathcal{X},\mu,T) and a set A ? XA\in\mathcal{X} of positive measure, the set of integers n such that A T^2nA T^knA)(A)^k+1-\mu(A{\cap} T^{n}A{\cap} T^{2n}A{\cap} \ldots{\cap} T^{kn}A)>\mu(A)^{k+1}-\epsilon is syndetic. The size of this set, surprisingly enough, depends on the length (k+1) of the arithmetic progression under consideration. In an ergodic system, for k=2 and k=3, this set is syndetic, while for kòf(x)f(Tⁿx)f(T²ⁿx)? f(T^knx)  dm(x)\int{f(x)f(T^{n}x)f(T^{2n}x){\ldots} f(T^{kn}x) \,d\mu(x)} , where k and n are positive integers and f is a bounded measurable function. We also derive combinatorial consequences of these results, for example showing that for a set of integers E with upper Banach density d^*(E)>0 and for all {n ? \mathbbZ\colon d^*(E?(E+n)?(E+2n)?(E+3n)) > d^*(E)⁴-e}\big\{n\in\mathbb{Z}{\colon} d^*\big(E\cap(E+n)\cap(E+2n)\cap(E+3n)\big) > d^*(E)^4-\epsilon\big\}     

Sequences realizable by maximal k-degenerate graphs

A graph G is called k-degenerate if every subgraph of G has a vertex of degree at most k. A k-degenerate graph G is maximal k-degenerate if for every edge e ? E(G), G + e is not k-degenerate. Necessary and sufficient conditions for the sequence II = (d₁, d₂, ?, d_p) to be a degree sequence of a maximal k-degenerate graph G are presented. © 1995 John Wiley & Sons, Inc.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

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.     

On 2-factors with given properties in claw-free graphs

Let G be a claw-free graph such that (i) k(G) 3 2k(G) \geq 2, (ii) $|V (G)| \geq 8$|V (G)| \geq 8 and (iii) d(G) 3 4\delta(G) \geq 4. For every pair of edges e₁, e₂ of G the graph G^* = G - {e₁, e₂}G^* = G - \{e_1, e_2\} has a 2-factor.     

Universal meromorphic approximation on Vitushkin sets

The paper proves the following result on universal meromorphic approximation: Given any unbounded sequence {λ _n } ? ?, there exists a function ?, meromorphic on ?, with the following property. For every compact set K of rational approximation (i.e. Vitushkin set), and every function f, continuous on K and holomorphic in the interior of K, there exists a subsequence {n _k } of ? such that $ \left\{ {\varphi \left( {z + \lambda _{n_k } } \right)} \right\} The paper proves the following result on universal meromorphic approximation: Given any unbounded sequence {λ _n } ⊂ ℂ, there exists a function ϕ, meromorphic on ℂ, with the following property. For every compact set K of rational approximation (i.e. Vitushkin set), and every function f, continuous on K and holomorphic in the interior of K, there exists a subsequence {n _k } of ℕ such that converges to f(z) uniformly on K. A similar result is obtained for arbitrary domains G ≠ ℂ. Moreover, in case {λ _n }={n} the function ϕ is frequently universal in terms of Bayart/Grivaux [3]. Original Russian Text ? W.Luh, T.Meyrath, M.Niess, 2008, published in Izvestiya NAN Armenii. Matematika, 2008, No. 6, pp. 66–75.     

Covering a graph with cycles passing through given edges

We propose a conjecture: for each integer k ≥ 2, there exists N(k) such that if G is a graph of order n ≥ N(k) and d(x) + d(y) ≥ n + 2k - 2 for each pair of non-adjacent vertices x and y of G, then for any k independent edges e₁, …, e_k of G, there exist k vertex-disjoint cycles C₁, …, C_k in G such that e_i ∈ E(C_i) for all i ∈ {1, …, k} and V(C₁ ∪ ···∪ C_k) = V(G). If this conjecture is true, the condition on the degrees of G is sharp. We prove this conjecture for the case k = 2 in the paper. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 105–109, 1997     

Full friendly index sets of Cartesian products of two cycles

Let G =（V, E） be a connected simple graph. A labeling f ： V → Z2 induces an edge labeling f＊ ： E → Z2 defined by f＊（xy） = f（x） ＋f（y） for each xy ∈ E. For i ∈ Z2, let vf（i） = ｜f^-1（i）｜ and ef（i） = ｜f＊^-1（i）｜. A labeling f is called friendly if ｜vf（1） - vf（0）｜ ≤ 1. For a friendly labeling f of a graph G, we define the friendly index of G under f by if（G） = e（1） - el（0）. The set [if（G） ｜ f is a friendly labeling of G} is called the full friendly index set of G, denoted by FFI（G）. In this paper, we will determine the full friendly index set of every Cartesian product of two cycles.     

Lower bounds on signed edge total domination numbers in graphs

The open neighborhood N _G (e) of an edge e in a graph G is the set consisting of all edges having a common end-vertex with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge total dominating function of G. The minimum of the values , taken over all signed edge total dominating function f of G, is called the signed edge total domination number of G and is denoted by γ _st ′(G). Obviously, γ _st ′(G) is defined only for graphs G which have no connected components isomorphic to K ₂. In this paper we present some lower bounds for γ _st ′(G). In particular, we prove that γ _st ′(T) ⩾ 2 − m/3 for every tree T of size m ⩾ 2. We also classify all trees T with γ _st ′(T). Research supported by a Faculty Research Grant, University of West Georgia.     

Some Notes on Signed Edge Domination in Graphs

The closed neighborhood N_G[e] of an edge e in a graph G is the set consisting of e and of all edges having an end-vertex in common with e. Let f be a function on E(G), the edge set of G, into the set {−1, 1}. If for each e ∈ E(G), then f is called a signed edge dominating function of G. The signed edge domination number γ_s^′(G) of G is defined as . Recently, Xu proved that γ_s^′(G) ≥ |V(G)| − |E(G)| for all graphs G without isolated vertices. In this paper we first characterize all simple connected graphs G for which γ_s^′(G) = |V(G)| − |E(G)|. This answers Problem 4.2 of [4]. Then we classify all simple connected graphs G with precisely k cycles and γ_s^′(G) = 1 − k, 2 − k. A. Khodkar: Research supported by a Faculty Research Grant, University of West Georgia. Send offprint requests to: Abdollah Khodkar.     

Iterative Methods for Fixed Points of Asymptotically Weakly Contractive Maps

Suppose K is a closed convex nonexpansive retract of a real uniformly smooth Banach space E with P as the nonexpansive retraction. Suppose T : K → E is an asymptotically d-weakly contractive map with sequence {k_n }, k_n ≥ 1, lim k_n = 1 and with F(T) _n int (K) ≠ ø F(T):= {x ∈ K: Tx = x}. Suppose {x _n } is iteratively defined by x _n+1 = P((l ? k_nα_n )x _n +k _n α _n T(PT) ^n?l x_n ), n = 1,2,...,x ₁ ∈ K, where α_n∈ (0,l) satisfies lim α_n = 0 and Σα_n = ∞. It is proved that {x _n } converges strongly to some x ^* ∈ F(T)∩ int K. Furthermore, if K is a closed convex subset of an arbitrary real Banach space and T is, in addition uniformly continuous, with F(T) ≠ ø, it is proved that {x_n } converges strongly to some x ^* ∈ F(T).     

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.     

The cycle space of an embedded graph

Let G be a connected graph with edge set E embedded in the surface ∑. Let G° denote the geometric dual of G. For a subset d of E, let τd denote the edges of G° that are dual to those edges of G in d. We prove the following generalizations of well-known facts about graphs embedded in the plane. (1) b is a boundary cycle in G if and only if τb is a cocycle in G°. (2) If T is a spanning tree of G, then τ(E/T) contains a spanning tree of G°. (3) Let T be any spanning tree of G and, for e ? E/T, let T(e) denote the fundamental cycle of e. Let U ∪ E/T. Then τU is a spanning tree of G° if and only if the set of face boundaries, less any one, together with the set {T(e); e ? E/(T ∪ U)} is a basis for the cycle space of G.     

Degree Bounded Spanning Trees

In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set ${S \subseteq V(G)}In this paper, we give a sufficient condition for a graph to have a degree bounded spanning tree. Let n ≥ 1, k ≥ 3, c ≥ 0 and G be an n-connected graph. Suppose that for every independent set S í V(G){S \subseteq V(G)} of cardinality n(k−1) + c + 2, there exists a vertex set X í S{X \subseteq S} of cardinality k such that the degree sum of vertices in X is at least |V(G)| − c −1. Then G has a spanning tree T with maximum degree at most k+éc/nù{k+\lceil c/n\rceil} and ?_{v ? V(T)}max{d_T(v)-k,0} ￡ c{\sum_{v\in V(T)}\max\{d_T(v)-k,0\}\leq c} .     

The {k}-domatic number of a graph

For a positive integer k, a {k}-dominating function of a graph G is a function f from the vertex set V(G) to the set {0, 1, 2, . . . , k} such that for any vertex ${v\in V(G)}$ , the condition ${\sum_{u\in N[v]}f(u)\ge k}$ is fulfilled, where N[v] is the closed neighborhood of v. A {1}-dominating function is the same as ordinary domination. A set {f ₁, f ₂, . . . , f _d } of {k}-dominating functions on G with the property that ${\sum_{i=1}^df_i(v)\le k}$ for each ${v\in V(G)}$ , is called a {k}-dominating family (of functions) on G. The maximum number of functions in a {k}-dominating family on G is the {k}-domatic number of G, denoted by d _{k}(G). Note that d _{1}(G) is the classical domatic number d(G). In this paper we initiate the study of the {k}-domatic number in graphs and we present some bounds for d _{k}(G). Many of the known bounds of d(G) are immediate consequences of our results.     

{k,r – k}-Factors of r-Regular Graphs

For a set \({\mathcal{S}}\) of positive integers, a spanning subgraph F of a graph G is called an \({\mathcal{S}}\) -factor of G if \({\deg_F(x) \in \mathcal{S}}\) for all vertices x of G, where deg _F (x) denotes the degree of x in F. We prove the following theorem on {a, b}-factors of regular graphs. Let r ≥ 5 be an odd integer and k be either an even integer such that 2 ≤ k < r/2 or an odd integer such that r/3 ≤ k < r/2. Then every r-regular graph G has a {k, r–k}-factor. Moreover, for every edge e of G, G has a {k, r–k}-factor containing e and another {k, r–k}-factor avoiding e.     

Orthogonal factorizations of graphs

Let G be a graph with vertex set V(G) and edge set E(G). Let k₁, k₂,…,k_m be positive integers. It is proved in this study that every [0,k₁+…+k_m?m+1]‐graph G has a [0, k_i]₁^m‐factorization orthogonal to any given subgraph H with m edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 267–276, 2002