Recurrent points and non-wandering points of graph maps

Let G be a graph and f:G→G be a continuous map. Denote by P(f), R(f) and Ω(f) the sets of periodic points, recurrent points and non-wandering points of f, respectively. In this paper we show that: (1) If L=(x,y) is an open arc contained in an edge of G such that {fm(x),fk(y)}⊂(x,y) for some m,k∈N, then R(f)∩(x,y)≠∅; (2) Any isolated point of P(f) is also an isolated point of Ω(f); (3) If x∈Ω(f)−Ω(fn) for some n∈N, then x is an eventually periodic point. These generalize the corresponding results in W. Huang and X. Ye (2001) [9] and J. Xiong (1983, 1986) [17] and [19] on interval maps or tree maps.     

Generalizing D-graphs

Let ω₀(G) denote the number of odd components of a graph G. The deficiency of G is defined as def(G)=max_X⊆V(G)(ω₀(G-X)-|X|), and this equals the number of vertices unmatched by any maximum matching of G. A subset X⊆V(G) is called a Tutte set (or barrier set) of G if def(G)=ω₀(G-X)-|X|, and an extreme set if def(G-X)=def(G)+|X|. Recently a graph operator, called the D-graph D(G), was defined that has proven very useful in examining Tutte sets and extreme sets of graphs which contain a perfect matching. In this paper we give two natural and related generalizations of the D-graph operator to all simple graphs, both of which have analogues for many of the interesting and useful properties of the original.     

Asymptotically stable sets and the stability of ω-limit sets

Let C be the collection of continuous self-maps of the unit interval I=[0,1] to itself. For f∈C and x∈I, let ω(x,f) be the ω-limit set of f generated by x, and following Block and Coppel, we take Q(x,f) to be the intersection of all the asymptotically stable sets of f containing ω(x,f). We show that Q(x,f) tells us quite a bit about the stability of ω(x,f) subject to perturbations of either x or f, or both. For example, a chain recurrent point y is contained in Q(x,f) if and only if there are arbitrarily small perturbations of f to a new function g that give us y as a point of ω(x,g). We also study the structure of the map Q taking (x,f)∈I×C to Q(x,f). We prove that Q is upper semicontinuous and a Baire 1 function, hence continuous on a residual subset of I×C. We also consider the map given by x?Q(x,f), and find that this map is continuous if and only if it is a constant map; that is, only when the set is a singleton.     

Linear transformations of monotone functions on the discrete cube

For a function f:{0,1}ⁿ→R and an invertible linear transformation L∈GL_n(2), we consider the function Lf:{0,1}ⁿ→R defined by Lf(x)=f(Lx). We raise two conjectures: First, we conjecture that if f is Boolean and monotone then I(Lf)≥I(f), where I(f) is the total influence of f. Second, we conjecture that if both f and L(f) are monotone, then f=L(f) (up to a permutation of the coordinates). We prove the second conjecture in the case where L is upper triangular.     

树映射的链回归点与拓扑熵

Let f be a tree map,P(f) the set of periodic points of f and CR(f) the set of chain recurrent points of f. In this paper,the notion of division for invariant closed subsets of a tree map is introduced. It is proved that: (1) fhas zero topological entropy if and only if for any x∈CR(f)-P(f) and each natural number s the orbit of x under f^5 has a division; (2) If f has zero topological entropy,then for any xECR(f)--P(f) the w-limit set of x is an infinite minimal set.     

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].     

Minimal rankings and the arank number of a path

Given a graph G, a function f:V(G)→{1,2,…,k} is a k-ranking of G if f(u)=f(v) implies every u-v path contains a vertex w such that f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The arank number of a graph, denoted ψ_r(G), is the largest k such that G has a minimal k-ranking. We present new results involving minimal k-rankings of paths. In particular, we determine ψ_r(P_n), a problem posed by Laskar and Pillone in 2000.     

The ω-limit set of a graph map

Let G be a graph and be continuous. Denote by P(f), , ω(f) and Ω(f) the set of periodic points, the closure of the set of periodic points, ω-limit set and non-wandering set of f, respectively. In this paper we show that: (1) v∈ω(f) if and only if v∈P(f) or there exists an open arc L=(v,w) contained in some edge of G such that every open arc U=(v,c)⊂L contains at least 2 points of some trajectory; (2) v∈ω(f) if and only if every open neighborhood of v contains at least r+1 points of some trajectory, where r is the valence of v; (3) ; (4) if , then x has an infinite orbit.     

Maximum nullity of outerplanar graphs and the path cover number

Let G=(V,E) be a graph with V={1,2,…,n}. Define S(G) as the set of all n×n real-valued symmetric matrices A=[a_ij] with a_ij≠0,i≠j if and only if ij∈E. By M(G) we denote the largest possible nullity of any matrix A∈S(G). The path cover number of a graph G, denoted P(G), is the minimum number of vertex disjoint paths occurring as induced subgraphs of G which cover all the vertices of G.There has been some success with relating the path cover number of a graph to its maximum nullity. Johnson and Duarte [5], have shown that for a tree T,M(T)=P(T). Barioli et al. [2], show that for a unicyclic graph G,M(G)=P(G) or M(G)=P(G)-1. Notice that both families of graphs are outerplanar. We show that for any outerplanar graph G,M(G)?P(G). Further we show that for any partial 2-path G,M(G)=P(G).     

Dual graph homomorphism functions

For any two graphs F and G, let hom(F,G) denote the number of homomorphisms F→G, that is, adjacency preserving maps V(F)→V(G) (graphs may have loops but no multiple edges). We characterize graph parameters f for which there exists a graph F such that f(G)=hom(F,G) for each graph G.The result may be considered as a certain dual of a characterization of graph parameters of the form hom(.,H), given by Freedman, Lovász and Schrijver [M. Freedman, L. Lovász, A. Schrijver, Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007) 37-51]. The conditions amount to the multiplicativity of f and to the positive semidefiniteness of certain matrices N(f,k).     

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.     

Scalar conservation laws with general boundary condition and continuous flux function

We introduce a notion of entropy solution for a scalar conservation law on a bounded domain with nonhomogeneous boundary condition: ut+divΦ(u)=f on Q=(0,T)×Ω, u(0,⋅)=u₀ on Ω and “u=a on some part of the boundary (0,T)×∂Ω.” Existence and uniqueness of the entropy solution is established for any Φ∈C(R;RN), u₀∈L^∞(Ω), f∈L^∞(Q), a∈L^∞((0,T)×∂Ω). In the L¹-setting, a corresponding result is proved for the more general notion of renormalised entropy solution.     

Roman and Total Domination

Abstract

A set S of vertices is a total dominating set of a graph G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set is the total domination number ^γt(G). A Roman dominating function on a graph G is a function f : V (G) → {0, 1, 2} satisfying the condition that every vertex u with f (u)=0 is adjacent to at least one vertex v of G for which f (v)=2. The minimum of f (V (G))=∑_{u ∈ V (G)} f (u) over all such functions is called the Roman domination number γR (G). We show that γt(G) ≤ γR (G) with equality if and only if ^γt(G)=2γ(G), where γ(G) is the domination number of G. Moreover, we characterize the extremal graphs for some graph families.     

A second-order estimate for blow-up solutions of elliptic equations

We investigate second-term asymptotic behavior of boundary blow-up solutions to the problems Δu=b(x)f(u), x∈Ω, subject to the singular boundary condition u(x)=∞, in a bounded smooth domain Ω⊂R^N. b(x) is a non-negative weight function. The nonlinearly f is regularly varying at infinity with index ρ>1 (that is lim_u→∞f(ξu)/f(u)=ξ^ρ for every ξ>0) and the mapping f(u)/u is increasing on (0,+∞). The main results show how the mean curvature of the boundary ∂Ω appears in the asymptotic expansion of the solution u(x). Our analysis relies on suitable upper and lower solutions and the Karamata regular variation theory.     

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].     

Coloring graphs from random lists of size 2

Let G=G(n) be a graph on n vertices with girth at least g and maximum degree bounded by some absolute constant Δ. Assign to each vertex v of G a list L(v) of colors by choosing each list independently and uniformly at random from all 2-subsets of a color set C of size σ(n). In this paper we determine, for each fixed g and growing n, the asymptotic probability of the existence of a proper coloring φ such that φ(v)∈L(v) for all v∈V(G). In particular, we show that if g is odd and σ(n)=ω(n^1/(2g−2)), then the probability that G has a proper coloring from such a random list assignment tends to 1 as n→∞. Furthermore, we show that this is best possible in the sense that for each fixed odd g and each n≥g, there is a graph H=H(n,g) with bounded maximum degree and girth g, such that if σ(n)=o(n^1/(2g−2)), then the probability that H has a proper coloring from such a random list assignment tends to 0 as n→∞. A corresponding result for graphs with bounded maximum degree and even girth is also given. Finally, by contrast, we show that for a complete graph on n vertices, the property of being colorable from random lists of size 2, where the lists are chosen uniformly at random from a color set of size σ(n), exhibits a sharp threshold at σ(n)=2n.     

Adding machines, kneading maps, and endpoints

Given a unimodal map f, let I=[c₂,c₁] denote the core and set E={(x₀,x₁,…)∈(I,f)|xi∈ω(c,f) for all i∈N}. It is known that there exist strange adding machines embedded in symmetric tent maps f such that the collection of endpoints of (I,f) is a proper subset of E and such that limk→∞Q(k)≠∞, where Q(k) is the kneading map.We use the partition structure of an adding machine to provide a sufficient condition for x to be an endpoint of (I,f) in the case of an embedded adding machine. We then show there exist strange adding machines embedded in symmetric tent maps for which the collection of endpoints of (I,f) is precisely E. Examples of this behavior are provided where limk→∞Q(k) does and does not equal infinity, and in the case where limk→∞Q(k)=∞, the collection of endpoints of (I,f) is always E.     

Matrix refinement type equations

Taking advantage of perpetuities and the asymptotic behavior of products of random matrices we obtain the direct form of the Fourier transform of an L¹-solution of the following random matrix refinement type equation

f(x)=_∫Ω|detL(ω)|C(ω)f(L(ω)x-M(ω))P(dω),     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.