Metric Dimension and R-Sets of Connected Graphs

The R-set relative to a pair of distinct vertices of a connected graph G is the set of vertices whose distances to these vertices are distinct. This paper deduces some properties of R-sets of connected graphs. It is shown that for a connected graph G of order n and diameter 2 the number of R-sets equal to V(G) is bounded above by ?n²/4?{\lfloor n^{2}/4\rfloor} . It is conjectured that this bound holds for every connected graph of order n. A lower bound for the metric dimension dim(G) of G is proposed in terms of a family of R-sets of G having the property that every subfamily containing at least r ≥ 2 members has an empty intersection. Three sufficient conditions, which guarantee that a family F=(G_n)_{n 3 1}{\mathcal{F}=(G_{n})_{n\geq 1}} of graphs with unbounded order has unbounded metric dimension, are also proposed.     

Families of pairs of graphs with a large number of common cards

The vertex‐deleted subgraph G?v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least \begin{eqnarray*}2\lfloor\frac{1}{3}(n-1)\rfloor\end{eqnarray*} common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have \begin{eqnarray*}\frac{2}{3}(n+5-2\sqrt{3n+6})\end{eqnarray*} common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n≥10. We also present infinite families of pairs of forests and pairs of trees with \begin{eqnarray*}2\lfloor\frac{1}{3}(n-4)\rfloor\end{eqnarray*} and \begin{eqnarray*}2\lfloor\frac{1}{3}(n-5)\rfloor\end{eqnarray*} common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146–163, 2010     

Triangle‐free subgraphs in the triangle‐free process

Consider the triangle‐free process, which is defined as follows. Start with G(0), an empty graph on n vertices. Given G(i ‐ 1), let G(i) = G(i ‐ 1) ∪{g(i)}, where g(i) is an edge that is chosen uniformly at random from the set of edges that are not in G(i ? 1) and can be added to G(i ‐ 1) without creating a triangle. The process ends once a maximal triangle‐free graph has been created. Let H be a fixed triangle‐free graph and let X_H(i) count the number of copies of H in G(i). We give an asymptotically sharp estimate for ??(X_H(i)), for every \begin{align*}1 \ll i \le 2^{-5} n^{3/2} \sqrt{\ln n}\end{align*}, at the limit as n →∞. Moreover, we provide conditions that guarantee that a.a.s. X_H(i) = 0, and that X_H(i) is concentrated around its mean.© 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On the Crossing Number of <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> □ <Emphasis Type="Italic">P</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript>

Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing number of the Cartesian products of paths, cycles or stars with small graphs. In this paper we study cr(K_m □ P_n), the crossing number of the Cartesian product K_m □ P_n. We prove that for m ≥ 3,n ≥ 1 and cr(K_m □ P_n)≥ (n − 1)cr(K_m+2 − e) + 2cr(K_m+1). For m≤ 5, according to Klešč, Jendrol and Ščerbová, the equality holds. In this paper, we also prove that the equality holds for m = 6, i.e., cr(K₆ □ P_n) = 15n + 3. Research supported by NFSC (60373096, 60573022).     

Balanced coloring of bipartite graphs

Given a bipartite graph G(U∪V, E) with n vertices on each side, an independent set I∈G such that |U∩I|=|V∩I| is called a balanced bipartite independent set. A balanced coloring of G is a coloring of the vertices of G such that each color class induces a balanced bipartite independent set in G. If graph G has a balanced coloring we call it colorable. The coloring number χ_B(G) is the minimum number of colors in a balanced coloring of a colorable graph G. We shall give bounds on χ_B(G) in terms of the average degree $\bar{d}$ of G and in terms of the maximum degree Δ of G. In particular we prove the following:

• $\chi_{{{B}}}({{G}}) \leq {{max}} \{{{2}},\lfloor {{2}}\overline{{{d}}}\rfloor+{{1}}\}$.
• For any 0<ε<1 there is a constant Δ₀ such that the following holds. Let G be a balanced bipartite graph with maximum degree Δ≥Δ₀ and n≥(1+ε)2Δ vertices on each side, then $\chi_{{{B}}}({{G}})\leq \frac{{{{20}}}}{\epsilon^{{{2}}}} \frac{\Delta}{{{{ln}}}\,\Delta}$.

© 2009 Wiley Periodicals, Inc. J Graph Theory 64: 277–291, 2010     

Boxicity of Circular Arc Graphs

A k-dimensional box is a Cartesian product R ₁ × · · · × R _k where each R _i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. That is, two vertices are adjacent if and only if their corresponding boxes intersect. A circular arc graph is a graph that can be represented as the intersection graph of arcs on a circle. We show that if G is a circular arc graph which admits a circular arc representation in which no arc has length at least p(\fraca-1a){\pi(\frac{\alpha-1}{\alpha})} for some a ? \mathbbN _{3 2}{\alpha\in\mathbb{N}_{\geq 2}}, then box(G) ≤ α (Here the arcs are considered with respect to a unit circle). From this result we show that if G has maximum degree D < ?\fracn(a-1)2a?{\Delta < \lfloor{\frac{n(\alpha-1)}{2\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha \in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. We also demonstrate a graph having box(G) > α but with D = n\frac(a-1)2a+ \fracn2a(a+1)+(a+2){\Delta=n\frac{(\alpha-1)}{2\alpha}+ \frac{n}{2\alpha(\alpha+1)}+(\alpha+2)}. For a proper circular arc graph G, we show that if D < ?\fracn(a-1)a?{\Delta < \lfloor{\frac{n(\alpha-1)}{\alpha}}\rfloor} for some a ? \mathbbN _{3 2}{\alpha\in \mathbb{N}_{\geq 2}}, then box(G) ≤ α. Let r be the cardinality of the minimum overlap set, i.e. the minimum number of arcs passing through any point on the circle, with respect to some circular arc representation of G. We show that for any circular arc graph G, box(G) ≤ r + 1 and this bound is tight. We show that if G admits a circular arc representation in which no family of k ≤ 3 arcs covers the circle, then box(G) ≤ 3 and if G admits a circular arc representation in which no family of k ≤ 4 arcs covers the circle, then box(G) ≤ 2. We also show that both these bounds are tight.     

Sums of Five, Seven and Nine Squares

Let r _k(n) denote the number of representations of an integer n as a sum of k squares. We prove that

Two classes of finite semigroups and monoids involving Lucas numbers

The class of finitely presented groups is an extension of the class of triangle groups studied recently. These groups are finite and their orders depend on the Lucas numbers. In this paper, by considering the three presentations

The upper traceable number of a graph

For a nontrivial connected graph G of order n and a linear ordering s: v ₁, v ₂, …, v _n of vertices of G, define . The traceable number t(G) of a graph G is t(G) = min{d(s)} and the upper traceable number t ⁺(G) of G is t ⁺(G) = max{d(s)}, where the minimum and maximum are taken over all linear orderings s of vertices of G. We study upper traceable numbers of several classes of graphs and the relationship between the traceable number and upper traceable number of a graph. All connected graphs G for which t ⁺(G) − t(G) = 1 are characterized and a formula for the upper traceable number of a tree is established. Research supported by Srinakharinwirot University, the Thailand Research Fund and the Commission on Higher Education, Thailand under the grant number MRG 5080075.     

On the chromatic number of random geometric graphs

Given independent random points X ₁,...,X _n ∈ℝ ^d with common probability distribution ν, and a positive distance r=r(n)>0, we construct a random geometric graph G _n with vertex set {1,..., n} where distinct i and j are adjacent when ‖X _i −X _j ‖≤r. Here ‖·‖ may be any norm on ℝ ^d , and ν may be any probability distribution on ℝ ^d with a bounded density function. We consider the chromatic number χ(G _n ) of G _n and its relation to the clique number ω(G _n ) as n→∞. Both McDiarmid [11] and Penrose [15] considered the range of r when $r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \ll \left( {\tfrac{{\ln n}} {n}} \right)^{1/d} and the range when $r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}$r \gg \left( {\tfrac{{\ln n}} {n}} \right)^{1/d}, and their results showed a dramatic difference between these two cases. Here we sharpen and extend the earlier results, and in particular we consider the ‘phase change’ range when $r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d}$r \sim \left( {\tfrac{{t\ln n}} {n}} \right)^{1/d} with t>0 a fixed constant. Both [11] and [15] asked for the behaviour of the chromatic number in this range. We determine constants c(t) such that $\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t)$\tfrac{{\chi (G_n )}} {{nr^d }} \to c(t) almost surely. Further, we find a “sharp threshold” (except for less interesting choices of the norm when the unit ball tiles d-space): there is a constant t ₀>0 such that if t≤t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to 1 almost surely, but if t>t ₀ then $\tfrac{{\chi (G_n )}} {{\omega (G_n )}}$\tfrac{{\chi (G_n )}} {{\omega (G_n )}} tends to a limit >1 almost surely.     

An Extension Of The Ruzsa-Szemerédi Theorem

  We let G ^(r)(n,m) denote the set of r-uniform hypergraphs with n vertices and m edges, and f ^(r)(n,p,s) is the smallest m such that every member of G ^(r)(n,m) contains amember of G ^(r)(p,s). In this paper we are interested in fixed values r,p and s for which f ^(r)(n,p,s) grows quadratically with n. A probabilistic construction of Brown, Erds and T. Sós ([2]) implies that f ^(r)(n,s(r-2)+2,s)=(n ²). In the other direction the most interesting question they could not settle was whether f ⁽³⁾(n,6, 3) = o(n ²). This was proved by Ruzsa and Szemerédi [11]. Then Erds, Frankl and Rödl [6] extended this result to any r: f ^(r)(n, 3(r-2)+3, 3)=o(n ²), and they conjectured ([4], [6]) that the Brown, Erds and T. Sós bound is best possible in the sense that f ^(r)(n,s(r-2)+3,s)=o(n ²).In this paper by giving an extension of the Erds, Frankl, Rödl Theorem (and thus the Ruzsa–Szemerédi Theorem) we show that indeed the Brown, Erds, T. Sós Theorem is not far from being best possible. Our main result is

Lebesgue property for convex risk measures on Orlicz spaces

We present a robust representation theorem for monetary convex risk measures r: X ? \mathbbR{\rho : \mathcal{X} \rightarrow \mathbb{R}} such that

On the mean square of Lerch zeta-functions

Using the approximate functional equation for L(l,a, s) = ?_n=0^￥ [(e(ln))/((n+a)^s)] L(\lambda,\alpha, s) = \sum\limits_{n=0}^{\infty} {e(\lambda n)\over (n+\alpha)^s} , we prove for fixed parameters $ 0<\lambda,\alpha\leq 1 $ 0<\lambda,\alpha\leq 1 asymptotic formulas for the mean square of L(l,a,s) L(\lambda,\alpha,s) inside the critical strip. This improves earlier results of D. Klusch and of A. Laurin)ikas.     

Packing Triangles in K 4-Free Graphs

Paul Erd?s conjectured that every K ₄-free graph of order n and size ${k + \lfloor n^2/4\rfloor}$ contains at least k edge disjoint triangles. In this note, we prove that such a graph contains at least 32k/35 + o(n ²) edge disjoint triangles and prove his conjecture for k ≥  0.077n ².     

Matching Polynomials And Duality

Let G be a simple graph on n vertices. An r-matching in G is a set of r independent edges. The number of r-matchings in G will be denoted by p(G, r). We set p(G, 0) = 1 and define the matching polynomial of G by and the signless matching polynomial of G by .It is classical that the matching polynomials of a graph G determine the matching polynomials of its complement . We make this statement more explicit by proving new duality theorems by the generating function method for set functions. In particular, we show that the matching functions and are, up to a sign, real Fourier transforms of each other.Moreover, we generalize Foatas combinatorial proof of the Mehler formula for Hermite polynomials to matching polynomials. This provides a new short proof of the classical fact that all zeros of µ(G, x) are real. The same statement is also proved for a common generalization of the matching polynomial and the rook polynomial.     

Hankel Determinants of Random Moment Sequences

For \(t \in [0,1]\) let \(\underline{H}_{2\lfloor nt \rfloor } = (m_{i+j})_{i,j=0}^{\lfloor nt \rfloor }\) denote the Hankel matrix of order \(2\lfloor nt \rfloor \) of a random vector \((m_1,\ldots ,m_{2n})\) on the moment space \(\mathcal {M}_{2n}(I)\) of all moments (up to the order 2n) of probability measures on the interval \(I \subset \mathbb {R}\). In this paper we study the asymptotic properties of the stochastic process \(\{ \log \det \underline{H}_{2\lfloor nt \rfloor } \}_{t\in [0,1]}\) as \(n \rightarrow \infty \). In particular weak convergence and corresponding large deviation principles are derived after appropriate standardization.     

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 ,}      18. 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)!!].      19. ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K1,8,n          下载免费PDF全文 黄元秋  赵霆雷 《数学物理学报(A辑)》2006,26(6):1115 The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph Km,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤ 6. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.      20. Packing k‐edge trees in graphs of restricted vertex degrees      A.K. Kelmans 《Journal of Graph Theory》2007,55(4):306-324 Let denote the set of graphs with each vertex of degree at least r and at most s, v(G) the number of vertices, and τk (G) the maximum number of disjoint k‐edge trees in G. In this paper we show that (a1) if G ∈ and s ≥ 4, then τ2(G) ≥ v(G)/(s + 1), (a2) if G ∈ and G has no 5‐vertex components, then τ2(G) ≥ v(G)4, (a3) if G ∈ and G has no k‐vertex component, where k ≥ 2 and s ≥ 3, then τk(G) ≥ (v(G) ‐k)/(sk ‐ k + 1), and (a4) the above bounds are attained for infinitely many connected graphs. Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007

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

ON THE CROSSING NUMBER OF THE COMPLETE TRIPARTITE GRAPH K1,8,n

The well known Zarankiewicz' conjecture is said that the crossing number of the complete bipartite graph K_m,n (m≤ n) is Z(m,n), where Z(m,n)=\lfloor\frac{m}{2}\rfloor\lfloor\frac{m-1}{2}\rfloor\lfloor\frac{n}{2}\rfloor$\lfloor\frac{n-1}{2}\rfloor$ (for any real number x, $\lfloor x\rfloor$ denotes the maximal integer no more than x). Presently, Zarankiewicz' conjecture is proved true only for the case m≤ 6. In this article, the authors prove that if Zarankiewicz' conjecture holds for m≤9, then the crossing number of the complete tripartite graph K_1,8,n is $Z(9, n)+ 12\lfloor\frac{n}{2}\rfloor$.     

Packing k‐edge trees in graphs of restricted vertex degrees

Let denote the set of graphs with each vertex of degree at least r and at most s, v(G) the number of vertices, and τ_k (G) the maximum number of disjoint k‐edge trees in G. In this paper we show that

• (a1) if G ∈ and s ≥ 4, then τ₂(G) ≥ v(G)/(s + 1),
• (a2) if G ∈ and G has no 5‐vertex components, then τ₂(G) ≥ v(G)4,
• (a3) if G ∈ and G has no k‐vertex component, where k ≥ 2 and s ≥ 3, then τ_k(G) ≥ (v(G) ‐k)/(sk ‐ k + 1), and
• (a4) the above bounds are attained for infinitely many connected graphs.

Our proofs provide polynomial time algorithms for finding the corresponding packings in a graph. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 306–324, 2007