Gauss-Bonnet Formula, Finiteness Condition, and Characterizations of Graphs Embedded in Surfaces

Let G be an infinite graph embedded in a closed 2-manifold, such that each open face of the embedding is homeomorphic to an open disk and is bounded by finite number of edges. For each vertex x of G, define the combinatorial curvature

Embedding graphs with bounded degree in sparse pseudorandom graphs

In this paper, we show the equivalence of somequasi-random properties for sparse graphs, that is, graphsG with edge densityp=|E(G)|/( ₂ ⁿ )=o(1), whereo(1)→0 asn=|V(G)|→∞. Our main result (Theorem 16) is the following embedding result. For a graphJ, writeN _J(x) for the neighborhood of the vertexx inJ, and letδ(J) andΔ(J) be the minimum and the maximum degree inJ. LetH be atriangle-free graph and setd _H=max{δ(J):J⊆H}. Moreover, putD _H=min{2d _H,Δ(H)}. LetC>1 be a fixed constant and supposep=p(n)≫n ⁻¹ D _H. We show that ifG is such that

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

The minimum degree threshold for perfect graph packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let δ(H,n) denote the smallest integer k such that every graph G whose order n is divisible by |H| and with δ(G)≥k contains a perfect H-packing. We show that

On the number of subgraphs of prescribed type of graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For a graphH=〈V(H),E(H)〉 and forS ⊂V(H) defineN(S)={x ∈V(H):xy ∈E(H) for somey ∈S}. Define alsoδ(H)= max {|S| − |N(S)|:S ⊂V(H)},γ(H)=1/2(|V(H)|+δ(H)). For two graphsG, H letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also forl>0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We investigate the asymptotic behaviour ofN(l, H) for fixedH asl tends to infinity. The main results are:Theorem A. For every graph H there are positive constants c ₁, c₂ such that {fx116-1}. Theorem B. If δ(H)=0then {fx116-2},where |AutH|is the number of automorphisms of H. (It turns out thatδ(H)=0 iffH has a spanning subgraph which is a disjoint union of cycles and isolated edges.) This paper forms part of an M.Sc. Thesis written by the author under the supervision of Prof. M. A. Perles from the Hebrew University of Jerusalem.     

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following

Strictly Hermitian positive definite functions

LetH be any complex inner product space with inner product <·,·>. We say thatf: ℂ→ℂ is Hermitian positive definite onH if the matrix

Relations entre isopérimétrie et trou spectral pour les chaînes de Markov finies

Let G be a finite and connected graph, we will note by l(G) the maximum length of an injective path in G. We will show (by two dictinct proofs, one using sub-trees of G and the other based on multiflows of paths) that sup _{(P,μ)∈?(G)} I(P, μ)/λ(P, μ) = l(G), where the supremum is taken over all Markovian kernels P reversible with respect to a probability μ and whose allowed transitions are given by the edges of G, and where I(P, μ) (respectively λ(P, μ)) is the isoperimetric constant (resp. the spectral gap) associated to the couple (P, μ). Then we will study more precisely the same supremum, but where the probability μ is also fixed. These results give optimal minorations of the spectral gap which are linear with respect to the isoperimetric constant (and not quadratic, as in the Cheeger inequality), and we will give several examples on infinite graphs. Re?u: 12 ao?t 1997 / Version révisée: 9 novembre 1998     

On the Diophantine Equation G n ( x )?= G m ( P ( x ))

 Let K be a field of characteristic 0 and let p, q, G ₀ , G ₁ , P ∈K[x], deg P ⩾ 1. Further, let the sequence of polynomials (G _n (x)) _n=0 ^∞ be defined by the second order linear recurring sequence

On the number of certain subgraphs contained in graphs with a given number of edges

All graphs considered are finite, undirected, with no loops, no multiple edges and no isolated vertices. For two graphsG, H, letN(G, H) denote the number of subgraphs ofG isomorphic toH. Define also, forl≧0,N(l, H)=maxN(G, H), where the maximum is taken over all graphsG withl edges. We determineN(l, H) precisely for alll≧0 whenH is a disjoint union of two stars, and also whenH is a disjoint union ofr≧3 stars, each of sizes ors+1, wheres≧r. We also determineN(l, H) for sufficiently largel whenH is a disjoint union ofr stars, of sizess ₁≧s ₂≧…≧s _r>r, provided (s ₁−s _r)²<s ₁+s _r−2r. We further show that ifH is a graph withk edges, then the ratioN(l, H)/l ^k tends to a finite limit asl→∞. This limit is non-zero iffH is a disjoint union of stars.     

Schur multiplicators of infinite pro-<Emphasis Type="Italic">p</Emphasis>-groups with finite coclass

Let G be an infinite pro-p-group of finite coclass and let M(G) be its Schur multiplicator. For p > 2, we determine the isomorphism type of Hom(M(G), ℤ_p), where ℤ_p denotes the p-adic integers, and show that M(G) is infinite. For p = 2, we investigate the Schur multiplicators of the infinite pro-2-groups of small coclass and show that M(G) can be infinite, finite or even trivial.     

Beurling's theorem and invariant subspaces for the shift on Hardy spaces

Let G be a bounded open subset in the complex plane and let H~2(G) denote the Hardy space on G. We call a bounded simply connected domain W perfectly connected if the boundary value function of the inverse of the Riemann map from W onto the unit disk D is almost 1-1 with respect to the Lebesgue measure on D and if the Riemann map belongs to the weak-star closure of the polynomials in H~∞(W). Our main theorem states: in order that for each M∈Lat (M_z), there exist u∈H~∞(G) such that M=∨{uH~2(G)}, it is necessary and sufficient that the following hold: (1) each component of G is a perfectly connected domain; (2) the harmonic measures of the components of G are mutually singular; (3) the set of polynomials is weak-star dense in H~∞(G). Moreover, if G satisfies these conditions, then every M∈Lat (M_z) is of the form uH~2(G), where u∈H~∞(G) and the restriction of u to each of the components of G is either an inner function or zero.     

On modules over integer-valued group rings of locally soluble groups with rank restrictions imposed on subgroups

We study a \mathbbZG \mathbb{Z}G -module A such that \mathbbZ \mathbb{Z} is the ring of integer numbers, the group G has an infinite sectional p-rank (or an infinite 0-rank), C _G (A) = 1, A is not a minimax \mathbbZ \mathbb{Z} -module, and, for any proper subgroup H of infinite sectional p-rank (or infinite 0-rank, respectively), the quotient module A/C _A (H) is a minimax \mathbbZ \mathbb{Z} -module. It is shown that if the group G is locally soluble, then it is soluble. Some properties of soluble groups of this kind are discussed.     

Pan-connectedness of graphs with large neighborhood unions

Let G be a simple graph with n vertices. For any v ? V(G){v \in V(G)} , let N(v)={u ? V(G): uv ? E(G)}{N(v)=\{u \in V(G): uv \in E(G)\}} , NC(G) = min{|N(u) èN(v)|: u, v ? V(G){NC(G)= \min \{|N(u) \cup N(v)|: u, v \in V(G)} and uv \not ? E(G)}{uv \not \in E(G)\}} , and NC₂(G) = min{|N(u) èN(v)|: u, v ? V(G){NC_2(G)= \min\{|N(u) \cup N(v)|: u, v \in V(G)} and u and v has distance 2 in E(G)}. Let l ≥ 1 be an integer. A graph G on n ≥ l vertices is [l, n]-pan-connected if for any u, v ? V(G){u, v \in V(G)} , and any integer m with l ≤ m ≤ n, G has a (u, v)-path of length m. In 1998, Wei and Zhu (Graphs Combinatorics 14:263–274, 1998) proved that for a three-connected graph on n ≥ 7 vertices, if NC(G) ≥ n − δ(G) + 1, then G is [6, n]-pan-connected. They conjectured that such graphs should be [5, n]-pan-connected. In this paper, we prove that for a three-connected graph on n ≥ 7 vertices, if NC ₂(G) ≥ n − δ(G) + 1, then G is [5, n]-pan-connected. Consequently, the conjecture of Wei and Zhu is proved as NC ₂(G) ≥ NC(G). Furthermore, we show that the lower bound is best possible and characterize all 2-connected graphs with NC ₂(G) ≥ n − δ(G) + 1 which are not [4, n]-pan-connected.     

Entropy bounds for perfect matchings and Hamiltonian cycles

For a graph G = (V,E) and x: E → ℜ⁺ satisfying Σ _e∋υ x _e = 1 for each υ ∈ V, set h(x) = Σ _e x _e log(1/x _e ) (with log = log₂). We show that for any n-vertex G, random (not necessarily uniform) perfect matching f satisfying a mild technical condition, and x _e =Pr(e∈f),

A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

On the Diophantine Equation G n ( x )?= G m ( P ( x ))

 Let K be a field of characteristic 0 and let p, q, G ₀ , G ₁ , P ∈K[x], deg P ⩾ 1. Further, let the sequence of polynomials (G _n (x)) _n=0 ^∞ be defined by the second order linear recurring sequence

On the equivalence of some conditions for weighted Hardy spaces

Let G ∈ H _σ ^p (ℂ₊), where H _σ ^p (ℂ₊) is the class of functions analytic in the half plane ℂ₊ = {z: Re z > 0} and such that