The edge-face coloring of graphs embedded in a surface of characteristic zero

Let G be a graph embedded in a surface of characteristic zero with maximum degree Δ. The edge-face chromatic number χ_ef(G) of G is the least number of colors such that any two adjacent edges, adjacent faces, incident edge and face have different colors. In this paper, we prove that χ_ef(G)≤Δ+1 if Δ≥13, χ_ef(G)≤Δ+2 if Δ≥12, χ_ef(G)≤Δ+3 if Δ≥4, and χ_ef(G)≤7 if Δ≤3.     

An extremal problem on non-full colorable graphs

For a given graph G of order n, a k-L(2,1)-labelling is defined as a function f:V(G)→{0,1,2,…k} such that |f(u)-f(v)|?2 when d_G(u,v)=1 and |f(u)-f(v)|?1 when d_G(u,v)=2. The L(2,1)-labelling number of G, denoted by λ(G), is the smallest number k such that G has a k-L(2,1)-labelling. The hole index ρ(G) of G is the minimum number of integers not used in a λ(G)-L(2,1)-labelling of G. We say G is full-colorable if ρ(G)=0; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with λ(G)=2m and ρ(G)=m, where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole L(2,1)-colorings, Discrete Appl. Math. 130 (2003) 513-519].     

Near automorphisms of cycles

Let f be a permutation of V(G). Define δ_f(x,y)=|d_G(x,y)-d_G(f(x),f(y))| and δ_f(G)=∑δ_f(x,y) over all the unordered pairs {x,y} of distinct vertices of G. Let π(G) denote the smallest positive value of δ_f(G) among all the permutations f of V(G). The permutation f with δ_f(G)=π(G) is called a near automorphism of G. In this paper, we study the near automorphisms of cycles C_n and we prove that π(C_n)=4⌊n/2⌋-4, moreover, we obtain the set of near automorphisms of C_n.     

On friendly index sets of 2-regular graphs

Let G be a graph with vertex set V and edge set E, and let A be an abelian group. A labeling f:V→A induces an edge labeling f^∗:E→A defined by f^∗(xy)=f(x)+f(y). For i∈A, let v_f(i)=card{v∈V:f(v)=i} and e_f(i)=card{e∈E:f^∗(e)=i}. A labeling f is said to be A-friendly if |v_f(i)−v_f(j)|≤1 for all (i,j)∈A×A, and A-cordial if we also have |e_f(i)−e_f(j)|≤1 for all (i,j)∈A×A. When A=Z₂, the friendly index set of the graph G is defined as {|e_f(1)−e_f(0)|:the vertex labelingf is Z₂-friendly}. In this paper we completely determine the friendly index sets of 2-regular graphs. In particular, we show that a 2-regular graph of order n is cordial if and only if n?2 (mod 4).     

On island sequences of labelings with a condition at distance two

An L(2,1)-labeling of a graph G is a function f from the vertex set of G to the set of nonnegative integers such that |f(x)−f(y)|≥2 if d(x,y)=1, and |f(x)−f(y)|≥1 if d(x,y)=2, where d(x,y) denotes the distance between the pair of vertices x,y. The lambda number of G, denoted λ(G), is the minimum range of labels used over all L(2,1)-labelings of G. An L(2,1)-labeling of G which achieves the range λ(G) is referred to as a λ-labeling. A hole of an L(2,1)-labeling is an unused integer within the range of integers used. The hole index of G, denoted ρ(G), is the minimum number of holes taken over all its λ-labelings. An island of a given λ-labeling of G with ρ(G) holes is a maximal set of consecutive integers used by the labeling. Georges and Mauro [J.P. Georges, D.W. Mauro, On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] inquired about the existence of a connected graph G with ρ(G)≥1 possessing two λ-labelings with different ordered sequences of island cardinalities. This paper provides an infinite family of such graphs together with their lambda numbers and hole indices. Key to our discussion is the determination of the path covering number of certain 2-sparse graphs, that is, graphs containing no pair of adjacent vertices of degree greater than 2.     

Improvement on Brooks' chromatic bound for a class of graphs

Brooks' Theorem says that if for a graph G,Δ(G)=n, then G is n-colourable, unless (1) n=2 and G has an odd cycle as a component, or (2) n>2 and K_n+1 is a component of G. In this paper we prove that if a graph G has none of some three graphs (K_1,3;K₅?e and H) as an induced subgraph and if Δ(G)?6 and d(G)<Δ(G), then χ(G)<Δ(G). Also we give examples to show that the hypothesis Δ(G)?6 can not be non-trivially relaxed and the graph K₅?e can not be removed from the hypothesis. Moreover, for a graph G with none of K_1,3;K₅?e and H as an induced subgraph, we verify Borodin and Kostochka's conjecture that if for a graph G,Δ(G)?9 and d(G)<Δ(G), then χ(G)<Δ(G).     

On reformulated Zagreb indices

The first and second reformulated Zagreb indices are defined respectively in terms of edge-degrees as EM₁(G)=∑_e∈Edeg(e)² and EM₂(G)=∑_e∼fdeg(e)deg(f), where deg(e) denotes the degree of the edge e, and e∼f means that the edges e and f are adjacent. We give upper and lower bounds for the first reformulated Zagreb index, and lower bounds for the second reformulated Zagreb index. Then we determine the extremal n-vertex unicyclic graphs with minimum and maximum first and second Zagreb indices, respectively. Furthermore, we introduce another generalization of Zagreb indices.     

List coloring of Cartesian products of graphs

A well-established generalization of graph coloring is the concept of list coloring. In this setting, each vertex v of a graph G is assigned a list L(v) of k colors and the goal is to find a proper coloring c of G with c(v)∈L(v). The smallest integer k for which such a coloring c exists for every choice of lists is called the list chromatic number of G and denoted by χ_l(G).We study list colorings of Cartesian products of graphs. We show that unlike in the case of ordinary colorings, the list chromatic number of the product of two graphs G and H is not bounded by the maximum of χ_l(G) and χ_l(H). On the other hand, we prove that χ_l(G×H)?min{χ_l(G)+col(H),col(G)+χ_l(H)}-1 and construct examples of graphs G and H for which our bound is tight.     

Unique response Roman domination in graphs

A function f:V(G)→{0,1,2} is a Roman dominating function if every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. A function f:V(G)→{0,1,2} with the ordered partition (V₀,V₁,V₂) of V(G), where V_i={v∈V(G)∣f(v)=i} for i=0,1,2, is a unique response Roman function if x∈V₀ implies |N(x)∩V₂|≤1 and x∈V₁∪V₂ implies that |N(x)∩V₂|=0. A function f:V(G)→{0,1,2} is a unique response Roman dominating function if it is a unique response Roman function and a Roman dominating function. The unique response Roman domination number of G, denoted by u_R(G), is the minimum weight of a unique response Roman dominating function. In this paper we study the unique response Roman domination number of graphs and present bounds for this parameter.     

Independence and coloring properties of direct products of some vertex-transitive graphs

Let α(G) and χ(G) denote the independence number and chromatic number of a graph G, respectively. Let G×H be the direct product graph of graphs G and H. We show that if G and H are circular graphs, Kneser graphs, or powers of cycles, then α(G×H)=max{α(G)|V(H)|,α(H)|V(G)|} and χ(G×H)=min{χ(G),χ(H)}.     

Clique Vertex Magic Cover of a Graph

Let G admit an H-edge covering and f : V èE ? {1,2,?,n+e}{f : V \cup E \to \{1,2,\ldots,n+e\}} be a bijective mapping for G then f is called H-edge magic total labeling of G if there is a positive integer constant m(f) such that each subgraph H _i , i = 1, . . . , r of G is isomorphic to H and f(H_i)=f(H)=S_{v ? V(Hi)}f(v)+S_{e ? E(Hi)} f(e)=m(f){f(H_i)=f(H)=\Sigma_{v \in V(H_i)}f(v)+\Sigma_{e \in E(H_i)} f(e)=m(f)}. In this paper we define a subgraph-vertex magic cover of a graph and give some construction of some families of graphs that admit this property. We show the construction of some C _n - vertex magic covered and clique magic covered graphs.     

The Hosoya polynomial decomposition for catacondensed benzenoid graphs

For a graph G with the vertex set V(G), we denote by d(u,v) the distance between vertices u and v in G, by d(u) the degree of vertex u. The Hosoya polynomial of G is H(G)=∑_{u,v}⊆V(G)x^d(u,v). The partial Hosoya polynomials of G are for positive integer numbers m and n. It is shown that H(G₁)−H(G₂)=x²(x+1)²(H₃₃(G₁)−H₃₃(G₂)),H₂₂(G₁)−H₂₂(G₂)=(x²+x−1)²(H₃₃(G₁)−H₃₃(G₂)) and H₂₃(G₁)−H₂₃(G₂)=2(x²+x−1)(H₃₃(G₁)−H₃₃(G₂)) for arbitrary catacondensed benzenoid graphs G₁ and G₂ with equal number of hexagons. As an application, we give an affine relationship between H(G) with two other distance-based polynomials constructed by Gutman [I. Gutman, Some relations between distance-based polynomials of trees, Bulletin de l’Académie Serbe des Sciences et des Arts (Cl. Math. Natur.) 131 (2005) 1-7].     

Chromaticity of certain tripartite graphs identified with a path

For a graph G, let P(G) be its chromatic polynomial. Two graphs G and H are chromatically equivalent if P(G)=P(H). A graph G is chromatically unique if P(H)=P(G) implies that H≅G. In this paper, we classify the chromatic classes of graphs obtained from K_2,2,2∪P_m(m?3), (K_2,2,2-e)∪P_m(m?5) and (K_2,2,2-2e)∪P_m(m?6) by identifying the end-vertices of the path P_m with any two vertices of K_2,2,2, K_2,2,2-e and K_2,2,2-2e, respectively, where e and 2e are, respectively, an edge and any two edges of K_2,2,2. As a by-product of this, we obtain some families of chromatically unique and chromatically equivalent classes of graphs.     

Companionship and knot group representations

A companionship argument is used to give a constructive geometric proof of a key result concerning the knot homomorph problem: Given elements μ and λ in a group G, is there a knot K in S³ and a surjective representation ρ:π₁(S³−K)→G, such that ρ(m)=μ and ρ(l)=λ, where m and l are the meridian and longitude of K. The result presented here is that if for some μ that normally generates G, the pair (μ,μⁿ) is realizable, where n is the order of H₁(G;Z, then the pair (v,vⁿ) is realizable for any normal generator v.     

Decomposition of Graphs into (g, f)-Factors

Let G be a multigraph, g and f be integer-valued functions defined on V(G). Then a graph G is called a (g, f)-graph if g(x)≤deg _G(x)≤f(x) for each x∈V(G), and a (g, f)-factor is a spanning (g, f)-subgraph. If the edges of graph G can be decomposed into (g, f)-factors, then we say that G is (g, f)-factorable. In this paper, we obtained some sufficient conditions for a graph to be (g, f)-factorable. One of them is the following: Let m be a positive integer, l be an integer with l=m (mod 4) and 0≤l≤3. If G is an -graph, then G is (g, f)-factorable. Our results imply several previous (g, f)-factorization results. Revised: June 11, 1998     

Periodic solutions for wave equations with variable coefficients with nonlinear localized damping

We discuss the existence of periodic solutions to the wave equation with variable coefficients utt−div(A(x)∇u)+ρ(x,ut)=f(x,t) with Dirichlet boundary condition. Here ρ(x,v) is a function like ρ(x,v)=a(x)g(v) with g^′(v)?0 where a(x) is nonnegative, being positive only in a neighborhood of a part of the domain.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

Second order estimates for large solutions of elliptic equations

This paper deals with the second term asymptotic behavior of large solutions to the problems Δu=b(x)f(u), x∈Ω, subject to the singular boundary condition u(x)=∞, x∈∂Ω, where Ω is a smooth bounded domain in R^N, and b(x) is a non-negative weight function. The absorption term f is regularly varying at infinite with index ρ>1 (that is lim_u→∞f(ξu)/f(u)=ξ^ρ for every ξ>0) and the mapping f(u)/u is increasing on (0,+∞). Our analysis relies on the Karamata regular variation theory.     

Group-valued continuous functions with the topology of pointwise convergence

Let G be a topological group with the identity element e. Given a space X, we denote by Cp(X,G) the group of all continuous functions from X to G endowed with the topology of pointwise convergence, and we say that X is: (a) G-regular if, for each closed set F⊆X and every point x∈X?F, there exist f∈Cp(X,G) and g∈G?{e} such that f(x)=g and f(F)⊆{e}; (b) G^?-regular provided that there exists g∈G?{e} such that, for each closed set F⊆X and every point x∈X?F, one can find f∈Cp(X,G) with f(x)=g and f(F)⊆{e}. Spaces X and Y are G-equivalent provided that the topological groups Cp(X,G) and Cp(Y,G) are topologically isomorphic.We investigate which topological properties are preserved by G-equivalence, with a special emphasis being placed on characterizing topological properties of X in terms of those of Cp(X,G). Since R-equivalence coincides with l-equivalence, this line of research “includes” major topics of the classical Cp-theory of Arhangel'ski? as a particular case (when G=R).We introduce a new class of TAP groups that contains all groups having no small subgroups (NSS groups). We prove that: (i) for a given NSS group G, a G-regular space X is pseudocompact if and only if Cp(X,G) is TAP, and (ii) for a metrizable NSS group G, a G^?-regular space X is compact if and only if Cp(X,G) is a TAP group of countable tightness. In particular, a Tychonoff space X is pseudocompact (compact) if and only if Cp(X,R) is a TAP group (of countable tightness). Demonstrating the limits of the result in (i), we give an example of a precompact TAP group G and a G-regular countably compact space X such that Cp(X,G) is not TAP.We show that Tychonoff spaces X and Y are T-equivalent if and only if their free precompact Abelian groups are topologically isomorphic, where T stays for the quotient group R/Z. As a corollary, we obtain that T-equivalence implies G-equivalence for every Abelian precompact group G. We establish that T-equivalence preserves the following topological properties: compactness, pseudocompactness, σ-compactness, the property of being a Lindelöf Σ-space, the property of being a compact metrizable space, the (finite) number of connected components, connectedness, total disconnectedness. An example of R-equivalent (that is, l-equivalent) spaces that are not T-equivalent is constructed.     

List coloring of graphs having cycles of length divisible by a given number

Let G be a graph and χ_l(G) denote the list chromatic number of G. In this paper we prove that for every graph G for which the length of each cycle is divisible by l (l≥3), χ_l(G)≤3.