Mean-Field Conditions for Percolation on Finite Graphs

Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if $\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}$ then the size of the largest component in p-bond-percolation with ${p =\frac{1+O(n^{-1/3})}{d-1}}Let {G _n } be a sequence of finite transitive graphs with vertex degree d = d(n) and |G _n | = n. Denote by p ^t (v, v) the return probability after t steps of the non-backtracking random walk on G _n . We show that if p ^t (v, v) has quasi-random properties, then critical bond-percolation on G _n behaves as it would on a random graph. More precisely, if

lim sup  n n1/3 ?t = 1n1/3 tpt(v,v) < ￥,\mathop {\rm {lim\, sup\,}} \limits_{n} n^{1/3} \sum\limits_{t = 1}^{n^{1/3}} {t{\bf p}^t(v,v) < \infty ,}      2. On signed distance-k-domination in graphs      Huaming Xing  Liang Sun  Xuegang Chen 《Czechoslovak Mathematical Journal》2006,56(1):229-238 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.      3. The 2-pebbling property for dense graphs      Ze Tu Gao  Jian Hua Yin 《数学学报(英文版)》2013,29(3):557-570 Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f(G) is the smallest number m such that for every distribution of m pebbles and every vertex v,a pebble can be moved to v. A graph G is said to have the 2-pebbling property if for any distribution with more than 2f(G) q pebbles, where q is the number of vertices with at least one pebble, it is possible,using pebbling moves, to get two pebbles to any vertex. Snevily conjectured that G(s,t) has the 2-pebbling property, where G(s, t) is a bipartite graph with partite sets of size s and t (s ≥ t). Similarly, the-pebbling number f (G) is the smallest number m such that for every distribution of m pebbles and every vertex v, pebbles can be moved to v. Herscovici et al. conjectured that f(G) ≤ 1.5n + 8-6 for the graph G with diameter 3, where n = |V (G)|. In this paper, we prove that if s ≥ 15 and G(s, t) has minimum degree at least (s+1)/ 2 , then f (G(s, t)) = s + t, G(s, t) has the 2-pebbling property and f (G(s, t)) ≤ s + t + 8(-1). In other words, we extend a result due to Czygrinow and Hurlbert, and show that the above Snevily conjecture and Herscovici et al. conjecture are true for G(s, t) with s ≥ 15 and minimum degree at least (s+1)/ 2 .      4. On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters      Hong Lin Xiao-feng Guo 《应用数学学报(英文版)》2007,23(1):155-160 Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].      5. Upper Embeddability,Girth and the Degree-Sum of Nonadjacent Vertices      Ouyang Zhangdong  Wang Jing  Huang Yuanqiu 《Graphs and Combinatorics》2009,25(2):253-264 Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds (1)  α(G) ≤ 2; (2)  α(G) ≥ 3, and for any three nonadjacent vertices v i  (i = 1,2,3), it has , then G is upper embeddable and the lower bound v − 3g + 7 is best possible. Similarly the result for 3-edge-connected simple graph with girth g and independence number α(G) is also obtained. Huang Yuanqiu: Partially supported by National Science Foundation of China (No. 10771062) and Program for New Century Excellent Talents in University (No. NCET-07-0276).      6. The early evolution of the H-free process      Tom Bohman  Peter Keevash 《Inventiones Mathematicae》2010,181(2):291-336 The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn1-(vH-2)/(eH-1)(logn)1/(eH-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K r,r with r≥5. When H is a complete graph K s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn2/(s+1)(logn)1-1/(eH-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.      7. Signed 2-independence in graphs      Michael A. Henning   《Discrete Mathematics》2002,250(1-3) A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted αs2(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for αs2(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for αs2(T) are established and the extremal graphs characterized. It is shown that αs2(G) can be arbitrarily large negative even for a cubic graph G.      8. The geodetic numbers of graphs and digraphs   总被引：1，自引：0，他引：1   Chang-hong LU~ 《中国科学A辑(英文版)》2007,50(8):1163-1172 For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.      9. Cleaning Random d-Regular Graphs with Brooms      Pawe? Pra?at 《Graphs and Combinatorics》2011,27(4):567-584 A model for cleaning a graph with brushes was recently introduced. Let α = (v 1, v 2, . . . , v n ) be a permutation of the vertices of G; for each vertex v i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N-(vi)={j: vj vi ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let ba(G)=?i=1n max{|N+(vi)|-|N-(vi)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max α b α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.      10. Stability for large forbidden subgraphs      Vladimir Nikiforov 《Journal of Graph Theory》2009,62(4):362-368 In this note we strengthen the stability theorem of Erd?s and Simonovits. Write Kr(s1, …, sr) for the complete r‐partite graph with classes of sizes s1, …, sr and Tr(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n2/2 satisfies one of the conditions: (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write Kr(s1, …, sr) for the complete r‐partite graph with classes of sizes s1, …, sr and Tr(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n2/2 satisfies one of the conditions: (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$; (b) G differs from Tr(n) in fewer than (ε1/3+c1/(3r+3))n2 edges. Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions: (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$; (b) G differs from Tr(n) in fewer than (ε1/4+c1/(8r+8))n2 edges. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009      11. Some Notes on Signed Edge Domination in Graphs      H.?Karami  S.?M.?Sheikholeslami  A.?KhodkarEmail author 《Graphs and Combinatorics》2008,24(1):29-35 The closed neighborhood NG[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.      12. On super vertex-graceful unicyclic graphs      Sin-Min Lee  Elo Leung  Ho Kuen Ng 《Czechoslovak Mathematical Journal》2009,59(1):1-22 A graph G with p vertices and q edges, vertex set V(G) and edge set E(G), is said to be super vertex-graceful (in short SVG), if there exists a function pair (f, f +) where f is a bijection from V(G) onto P, f + is a bijection from E(G) onto Q, f +((u, v)) = f(u) + f(v) for any (u, v) ∈ E(G), and We determine here families of unicyclic graphs that are super vertex-graceful.       13. A New Bound on the Total Domination Subdivision Number      O. Favaron  H. Karami  R. Khoeilar  S. M. Sheikholeslami 《Graphs and Combinatorics》2009,25(1):41-47 A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number 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 total domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3, where d 2(v) is the number of vertices of G at distance 2 from v. R. Khoeilar: Research supported by the Research Office of Azarbaijan University of Tarbiat Moallem.      14. The hull and geodetic numbers of orientations of graphs      Jung-Ting Hung  Hong-Tsu Wang 《Discrete Mathematics》2009,309(8):2134-2139 For an oriented graph D, let ID[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let ID[S] denote the union of all ID[u,v] for all u,v∈S. Let [S]D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with ID[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g−(G)=min{g(D):D∈O(G)}, g+(G)=max{g(D):D∈O(G)}, h−(G)=min{h(D):D∈O(G)}, and h+(G)=max{h(D):D∈O(G)}. By the above definitions, h−(G)≤g−(G) and h+(G)≤g+(G). In the paper, we prove that g−(G)<h+(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g−(G)−h−(G)=a and g+(G)−h+(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].      15. Sequential Dynamical Systems Over Words      C. M. Reidys 《Annals of Combinatorics》2006,10(4):481-498 In this paper we study sequential dynamical systems (SDS) over words. An SDS is a triple consisting of: (a) a graph Y with vertex set {v1, ..., vn}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w1, ..., wk), where wi is a Y-vertex. A map is called Y-local if and only if it fixes all variables and depends exclusively on the variables , for . An SDS induces an SDS- map, , obtained by the map-composition of the functions according to w. We show that an SDS induces in addition the graph G(w,Y) having vertex set {1, ..., k} where r, s are adjacent if and only if ws, wr are adjacent in Y. G(w, Y) is acted upon by Sk via and Fix(w) is the group of G(w, Y) graph automorphisms which fix w. We analyze G(w, Y)-automorphisms via an exact sequence involving the normalizer of Fix(w) in Aut(G(w, Y)), Fix(w) and Aut(Y). Furthermore we introduce an equivalence relation over words and prove a bijection between word equivalence classes and certain orbits of acyclic orientations of G(w, Y). Received September 12, 2004      16. The Roman <Emphasis Type="Italic">k</Emphasis>-domatic number of a graph      Seyed Mahmoud Sheikholeslami  Lutz Volkmann 《数学学报(英文版)》2011,27(10):1899-1906 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 1, f 2, …, 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.      17. Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K 12s+7      Ren Han  Gao Yanbo 《Graphs and Combinatorics》2011,27(2):187-197 In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least \frac14gM(G)?v ? V(G)(d(v)-1)!{\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}} distinct MGE’s, where γ M (G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119–126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G s of K 12s+7, then G s has at least 23s distinct MGE’s.This implies that K 12s+7 has at least (22) s nonisomorphic cyclic oriented triangular embeddings for sufficient large s.      18. Rooted induced trees in triangle‐free graphs      Florian Pfender 《Journal of Graph Theory》2010,64(3):206-209 For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t3(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010      19. Independent edges in bipartite graphs obtained from orientations of graphs      J. G. Gimbel  K. B. Reid 《Journal of Graph Theory》1994,18(5):515-533 Given a digraph D on vertices v1, v2, ?, vn, we can associate a bipartite graph B(D) on vertices s1, s2, ?, sn, t1, t2, ?, tn, where sitj is an edge of B(D) if (vi, vj) is an arc in D. Let OG denote the set of all orientations on the (undirected) graph G. In this paper we will discuss properties of the set S(G) := {β1 (B(D))) | D ? OG}, where β1 is the edge independence number. In the first section we present some background and related concepts. We show that sets of the form S(G) are convex and that max S(G) ≦ 2 min S(G). Furthermore, this completely characterizes such sets. In the second section we discuss some bounds on elements of S(G) in terms of more familiar graphical parameters. The third section deals with extremal problems. We discuss bounds on elements of S(G) if the order and size of G are known, particularly when G is bipartite. In this section we exhibit a relation between max S(G) and the concept of graphical closure. In the fourth and final section we discuss the computational complexity of computing min S(G) and max S(G). We show that the first problem is NP-complete and that the latter is polynomial.      20. Quasi-periodic solutions for the general semilinear Duffing equations with asymmetric nonlinearity and oscillating potential      Zhang  Xinli  Peng  Yaqun  Piao  Daxiong 《中国科学 数学(英文版)》2021,64(5):931-946 In this paper,we prove the existence of quasi-periodic solutions and the boundedness of all the solutions of the general semilinear quasi-periodic differential equation x′′+ax~+-bx~-=G_x(x,t)+f (t),where x~+=max{x,0},x~-=max{-x,0},a and b are two different positive constants,f(t) is C~(39) smooth in t,G(x,t)is C~(35) smooth in x and t,f (t) and G(x,t) are quasi-periodic in t with the Diophantine frequency ω=(ω_1,ω_2),and D_x~iD_t~jG(x,t) is bounded for 0≤i+j≤35.

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 2-pebbling property for dense graphs

Given a distribution of pebbles on the vertices of a connected graph G, a pebbling move on G consists of taking two pebbles off one vertex and placing one on an adjacent vertex. The pebbling number f(G) is the smallest number m such that for every distribution of m pebbles and every vertex v,a pebble can be moved to v. A graph G is said to have the 2-pebbling property if for any distribution with more than 2f(G) q pebbles, where q is the number of vertices with at least one pebble, it is possible,using pebbling moves, to get two pebbles to any vertex. Snevily conjectured that G(s,t) has the 2-pebbling property, where G(s, t) is a bipartite graph with partite sets of size s and t (s ≥ t). Similarly, the-pebbling number f (G) is the smallest number m such that for every distribution of m pebbles and every vertex v, pebbles can be moved to v. Herscovici et al. conjectured that f(G) ≤ 1.5n + 8-6 for the graph G with diameter 3, where n = |V (G)|. In this paper, we prove that if s ≥ 15 and G(s, t) has minimum degree at least (s+1)/ 2 , then f (G(s, t)) = s + t, G(s, t) has the 2-pebbling property and f (G(s, t)) ≤ s + t + 8(-1). In other words, we extend a result due to Czygrinow and Hurlbert, and show that the above Snevily conjecture and Herscovici et al. conjecture are true for G(s, t) with s ≥ 15 and minimum degree at least (s+1)/ 2 .     

On the Upper Bounds of the Numbers of Perfect Matchings in Graphs with Given Parameters

Let φ(G),κ(G),α(G),χ(G),cl(G),diam(G)denote the number of perfect matchings,connectivity,independence number,chromatic number,clique number and diameter of a graph G,respectively.In this note,by constructing some extremal graphs,the following extremal problems are solved:1.max{φ(G):|V(G)|=2n,κ(G)≤k}=k[(2n-3)!!],2.max{φ(G):|V(G)|=2n,α(G)≥k}=[multiply from i=0 to k-1(2n-k-i)[(2n-2k-1)!!],3.max{φ(G):|V(G)|=2n,χ(G)≤k}=φ(T_(k,2n))T_(k,2n)is the Turán graph,that is a complete k-partite graphon 2n vertices in which all parts are as equal in size as possible,4.max{φ(G):|V(G)|=2n,cl(G)=2}=n1,5.max{φ(G):|V(G)|=2n,diam(G)≥2}=(2n-2)(2n-3)[(2n-5)!!],max{φ(G):|V(G)|=2n,diam(G)≥3}=(n-1)~2[(2n-5)!!].     

Upper Embeddability,Girth and the Degree-Sum of Nonadjacent Vertices

Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds

The early evolution of the H-free process

The H-free process, for some fixed graph H, is the random graph process defined by starting with an empty graph on n vertices and then adding edges one at a time, chosen uniformly at random subject to the constraint that no H subgraph is formed. Let G be the random maximal H-free graph obtained at the end of the process. When H is strictly 2-balanced, we show that for some c>0, with high probability as n→∞, the minimum degree in G is at least cn^{1-(v_H-2)/(e_H-1)}(logn)^1/(e_H-1)cn^{1-(v_{H}-2)/(e_{H}-1)}(\log n)^{1/(e_{H}-1)}. This gives new lower bounds for the Turán numbers of certain bipartite graphs, such as the complete bipartite graphs K _r,r with r≥5. When H is a complete graph K _s with s≥5 we show that for some C>0, with high probability the independence number of G is at most Cn^2/(s+1)(logn)^1-1/(e_H-1)Cn^{2/(s+1)}(\log n)^{1-1/(e_{H}-1)}. This gives new lower bounds for Ramsey numbers R(s,t) for fixed s≥5 and t large. We also obtain new bounds for the independence number of G for other graphs H, including the case when H is a cycle. Our proofs use the differential equations method for random graph processes to analyse the evolution of the process, and give further information about the structure of the graphs obtained, including asymptotic formulae for a broad class of subgraph extension variables.     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

The geodetic numbers of graphs and digraphs

For every two vertices u and v in a graph G,a u-v geodesic is a shortest path between u and v.Let I(u,v)denote the set of all vertices lying on a u-v geodesic.For a vertex subset S,let I(S) denote the union of all I(u,v)for u,v∈S.The geodetic number g(G)of a graph G is the minimum cardinality of a set S with I(S)=V(G).For a digraph D,there is analogous terminology for the geodetic number g(D).The geodetic spectrum of a graph G,denoted by S(G),is the set of geodetic numbers of all orientations of graph G.The lower geodetic number is g~-(G)=minS(G)and the upper geodetic number is g~ (G)=maxS(G).The main purpose of this paper is to study the relations among g(G),g~-(G)and g~ (G)for connected graphs G.In addition,a sufficient and necessary condition for the equality of g(G)and g(G×K_2)is presented,which improves a result of Chartrand,Harary and Zhang.     

Cleaning Random d-Regular Graphs with Brooms

A model for cleaning a graph with brushes was recently introduced. Let α = (v ₁, v ₂, . . . , v _n ) be a permutation of the vertices of G; for each vertex v _i let ${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}}${N^+(v_i)=\{j: v_j v_i \in E {\rm and} j>\,i\}} and N^-(v_i)={j: v_j v_i ? E and j <  i}{N^-(v_i)=\{j: v_j v_i \in E {\rm and} j<\,i\}} ; finally let b_a(G)=?_i=1ⁿ max{|N⁺(v_i)|-|N^-(v_i)|,0}{b_{\alpha}(G)=\sum_{i=1}^n {\rm max}\{|N^+(v_i)|-|N^-(v_i)|,0\}}. The Broom number is given by B(G) =  max _α b _α (G). We consider the Broom number of d-regular graphs, focusing on the asymptotic number for random d-regular graphs. Various lower and upper bounds are proposed. To get an asymptotically almost sure lower bound we use a degree-greedy algorithm to clean a random d-regular graph on n vertices (with dn even) and analyze it using the differential equations method (for fixed d). We further show that for any d-regular graph on n vertices there is a cleaning sequence such at least n(d + 1)/4 brushes are needed to clean a graph using this sequence. For an asymptotically almost sure upper bound, the pairing model is used to show that at most n(d+2?{d ln2})/4{n(d+2\sqrt{d \ln 2})/4} brushes can be used when a random d-regular graph is cleaned. This implies that for fixed large d, the Broom number of a random d-regular graph on n vertices is asymptotically almost surely \fracn4(d+Q(?d)){\frac{n}{4}(d+\Theta(\sqrt{d}))}.     

Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:

• (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)In this note we strengthen the stability theorem of Erd?s and Simonovits. Write K_r(s₁, …, s_r) for the complete r‐partite graph with classes of sizes s₁, …, s_r and T_r(n) for the r‐partite Turán graph of order n. Our main result is: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with e(G)>(1?1/r?ε)n²/2 satisfies one of the conditions:
  • (a) G contains a $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/3+c^1/(3r+3))n² edges.
  Letting µ(G) be the spectral radius of G, we prove also a spectral stability theorem: For all r≥2 and all sufficiently small c>0, ε>0, every graph G of sufficiently large order n with µ(G)>(1?1/r?ε)n satisfies one of the conditions:
  • (a) G contains a $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$;
  • (b) G differs from T_r(n) in fewer than (ε^1/4+c^1/(8r+8))n² edges.
  © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009     

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.     

On super vertex-graceful unicyclic graphs

A graph G with p vertices and q edges, vertex set V(G) and edge set E(G), is said to be super vertex-graceful (in short SVG), if there exists a function pair (f, f ⁺) where f is a bijection from V(G) onto P, f ⁺ is a bijection from E(G) onto Q, f ⁺((u, v)) = f(u) + f(v) for any (u, v) ∈ E(G),

A New Bound on the Total Domination Subdivision Number

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number 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 total domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3,

The hull and geodetic numbers of orientations of graphs

For an oriented graph D, let I_D[u,v] denote the set of all vertices lying on a u-v geodesic or a v-u geodesic. For S⊆V(D), let I_D[S] denote the union of all I_D[u,v] for all u,v∈S. Let [S]_D denote the smallest convex set containing S. The geodetic number g(D) of an oriented graph D is the minimum cardinality of a set S with I_D[S]=V(D) and the hull number h(D) of an oriented graph D is the minimum cardinality of a set S with [S]_D=V(D). For a connected graph G, let O(G) be the set of all orientations of G, define g⁻(G)=min{g(D):D∈O(G)}, g⁺(G)=max{g(D):D∈O(G)}, h⁻(G)=min{h(D):D∈O(G)}, and h⁺(G)=max{h(D):D∈O(G)}. By the above definitions, h⁻(G)≤g⁻(G) and h⁺(G)≤g⁺(G). In the paper, we prove that g⁻(G)<h⁺(G) for a connected graph G of order at least 3, and for any nonnegative integers a and b, there exists a connected graph G such that g⁻(G)−h⁻(G)=a and g⁺(G)−h⁺(G)=b. These results answer a problem of Farrugia in [A. Farrugia, Orientable convexity, geodetic and hull numbers in graphs, Discrete Appl. Math. 148 (2005) 256-262].     

Sequential Dynamical Systems Over Words

In this paper we study sequential dynamical systems (SDS) over words. An SDS is a triple consisting of: (a) a graph Y with vertex set {v₁, ..., v_n}, (b) a family of Y-local functions , where K is a finite field and (c) a word w, i.e., a family (w₁, ..., w_k), where w_i is a Y-vertex. A map is called Y-local if and only if it fixes all variables and depends exclusively on the variables , for . An SDS induces an SDS- map, , obtained by the map-composition of the functions according to w. We show that an SDS induces in addition the graph G(w,Y) having vertex set {1, ..., k} where r, s are adjacent if and only if w_s, w_r are adjacent in Y. G(w, Y) is acted upon by S_k via and Fix(w) is the group of G(w, Y) graph automorphisms which fix w. We analyze G(w, Y)-automorphisms via an exact sequence involving the normalizer of Fix(w) in Aut(G(w, Y)), Fix(w) and Aut(Y). Furthermore we introduce an equivalence relation over words and prove a bijection between word equivalence classes and certain orbits of acyclic orientations of G(w, Y). Received September 12, 2004     

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.     

Lower Bound of the Number of Maximum Genus Embeddings and Genus Embeddings of K 12s+7

In this paper, we study lower bound of the number of maximum orientable genus embeddings (or MGE in short) for a loopless graph. We show that a connected loopless graph of order n has at least \frac14^g_M(G)?_{v ? V(G)}(d(v)-1)!{\frac{1}{4^{\gamma_M(G)}}\prod_{v\in{V(G)}}{(d(v)-1)!}} distinct MGE’s, where γ _M (G) is the maximum orientable genus of G. Infinitely many examples show that this bound is sharp (i.e., best possible) for some types of graphs. Compared with a lower bound of Stahl (Eur J Combin 13:119–126, 1991) which concerns upper-embeddable graphs (i.e., embedded graphs with at most two facial walks), this result is more general and effective in the case of (sparse) graphs permitting relative small-degree vertices. We also obtain a similar formula for maximum nonorientable genus embeddings for general graphs. If we apply our orientable results to the current graph G _s of K _12s+7, then G _s has at least 2^3s distinct MGE’s.This implies that K _12s+7 has at least (22) ^s nonisomorphic cyclic oriented triangular embeddings for sufficient large s.     

Rooted induced trees in triangle‐free graphs

For a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceilFor a graph G, let t(G) denote the maximum number of vertices in an induced subgraph of Gthat is a tree. Further, for a vertex v∈V(G), let t(G, v) denote the maximum number of vertices in an induced subgraph of Gthat is a tree, with the extra condition that the tree must contain v. The minimum of t(G) (t(G, v), respectively) over all connected triangle‐free graphs G(and vertices v∈V(G)) on nvertices is denoted by t₃(n) (t(n)). Clearly, t(G, v)?t(G) for all v∈V(G). In this note, we solve the extremal problem of maximizing |G| for given t(G, v), given that Gis connected and triangle‐free. We show that and determine the unique extremal graphs. Thus, we get as corollary that $t_3(n)\ge t_3^{\ast}(n) = \lceil {\frac{1}{2}}(1+{\sqrt{8n-7}})\rceil$, improving a recent result by Fox, Loh and Sudakov. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 206–209, 2010     

Independent edges in bipartite graphs obtained from orientations of graphs

Given a digraph D on vertices v₁, v₂, ?, v_n, we can associate a bipartite graph B(D) on vertices s₁, s₂, ?, s_n, t₁, t₂, ?, t_n, where s_it_j is an edge of B(D) if (v_i, v_j) is an arc in D. Let O_G denote the set of all orientations on the (undirected) graph G. In this paper we will discuss properties of the set S(G) := {β₁ (B(D))) | D ? O_G}, where β₁ is the edge independence number. In the first section we present some background and related concepts. We show that sets of the form S(G) are convex and that max S(G) ≦ 2 min S(G). Furthermore, this completely characterizes such sets. In the second section we discuss some bounds on elements of S(G) in terms of more familiar graphical parameters. The third section deals with extremal problems. We discuss bounds on elements of S(G) if the order and size of G are known, particularly when G is bipartite. In this section we exhibit a relation between max S(G) and the concept of graphical closure. In the fourth and final section we discuss the computational complexity of computing min S(G) and max S(G). We show that the first problem is NP-complete and that the latter is polynomial.     

Quasi-periodic solutions for the general semilinear Duffing equations with asymmetric nonlinearity and oscillating potential

In this paper,we prove the existence of quasi-periodic solutions and the boundedness of all the solutions of the general semilinear quasi-periodic differential equation x′′+ax~+-bx~-=G_x(x,t)+f (t),where x~+=max{x,0},x~-=max{-x,0},a and b are two different positive constants,f(t) is C~(39) smooth in t,G(x,t)is C~(35) smooth in x and t,f (t) and G(x,t) are quasi-periodic in t with the Diophantine frequency ω=(ω_1,ω_2),and D_x~iD_t~jG(x,t) is bounded for 0≤i+j≤35.