A new sufficient condition for Hamiltonian graphs

The study of Hamiltonian graphs began with Dirac’s classic result in 1952. This was followed by that of Ore in 1960. In 1984 Fan generalized both these results with the following result: If G is a 2-connected graph of order n and max{d(u),d(v)}≥n/2 for each pair of vertices u and v with distance d(u,v)=2, then G is Hamiltonian. In 1991 Faudree–Gould–Jacobson–Lesnick proved that if G is a 2-connected graph and |N(u)∪N(v)|+δ(G)≥n for each pair of nonadjacent vertices u,v∈V(G), then G is Hamiltonian. This paper generalizes the above results when G is 3-connected. We show that if G is a 3-connected graph of order n and max{|N(x)∪N(y)|+d(u),|N(w)∪N(z)|+d(v)}≥n for every choice of vertices x,y,u,w,z,v such that d(x,y)=d(y,u)=d(w,z)=d(z,v)=d(u,v)=2 and where x,y and u are three distinct vertices and w,z and v are also three distinct vertices (and possibly |{x,y}∩{w,z}| is 1 or 2), then G is Hamiltonian.     

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.     

Essential subgroups of topological groups

We study the class Wof Hausdorff topological groups Gfor which the following two cardinal invariants coincide

ES(G)=min{|H|:H≤ Gdense and essential}

TD(G)=min{|H|:H≤ Gtotally dense}

We prove that W contains the following classes:locally compact abelian groups, compact connected groups, countably compact totally discon¬nected abelian groups, topologically simple groups, locally compact Abelian groups when endowed with their Bohr topology, totally minimal abelian groups and free Abelian topological groups. For all these classes we are also able to giv ean explicit computation of the common value of ESand TD.     

On the Szeged and the Laplacian Szeged spectrum of a graph

For a given graph G its Szeged weighting is defined by w(e)=n_u(e)n_v(e), where e=uv is an edge of G,n_u(e) is the number of vertices of G closer to u than to v, and n_v(e) is defined analogously. The adjacency matrix of a graph weighted in this way is called its Szeged matrix. In this paper we determine the spectra of Szeged matrices and their Laplacians for several families of graphs. We also present sharp upper and lower bounds on the eigenvalues of Szeged matrices of graphs.     

The asymptotic distribution of weighted empirical distribution functions

Let G_n denote the empirical distribution based on n independent uniform (0, 1) random variables. The asymptotic distribution of the supremum of weighted discrepancies between G_n(u) and u of the forms 6w_v(u)D_n(u)6 and 6w_v(G_n(u))D_n(u)6, where D_n(u) = G_n(u)?u, w_v(u) = (u(1?u))^?1+v and 0 ? v < $\text{1}\text{2}$ is obtained. Goodness-of-fit tests based on these statistics are shown to be asymptotically sensitive only in the extreme tails of a distribution, which is exactly where such statistics that use a weight function w_v with $\text{1}\text{2}$ ? v ? 1 are insensitive. For this reason weighted discrepancies which use the weight function w_v with 0 ? v < $\text{1}\text{2}$ are potentially applicable in the construction of confidence contours for the extreme tails of a distribution.     

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.     

On the eccentric distance sum of trees and unicyclic graphs

Let G be a simple connected graph with the vertex set V(G). The eccentric distance sum of G is defined as ξd(G)=_∑v∈V(G)ε(v)DG(v), where ε(v) is the eccentricity of the vertex v and DG(v)=_∑u∈V(G)d(u,v) is the sum of all distances from the vertex v. In this paper we characterize the extremal unicyclic graphs among n-vertex unicyclic graphs with given girth having the minimal and second minimal eccentric distance sum. In addition, we characterize the extremal trees with given diameter and minimal eccentric distance sum.     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000     

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

A short proof of Fan's theorem

In this note, we give a new short proof of the following theorem: Let G be a 2-connected graph of order n. If for any two vertices u and v with d(u,v)=2,max{d(u),d(v)}?c/2, then the circumference of G is at least c, where 3?c?n and d(u,v) is the distance between u and v in G.     

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

Finite range decompositions of positive-definite functions

We give sufficient conditions for a positive-definite function to admit decomposition into a sum of positive-definite functions which are compactly supported within disks of increasing diameters Ln. More generally we consider positive-definite bilinear forms f→v(f,f) defined on . We say v has a finite range decomposition if v can be written as a sum v=∑Gn of positive-definite bilinear forms Gn such that Gn(f,g)=0 when the supports of the test functions f,g are separated by a distance greater or equal to Ln. We prove that such decompositions exist when v is dual to a bilinear form φ→∫²|Bφ| where B is a vector valued partial differential operator satisfying some regularity conditions.     

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.     

Finite Groups with S-permutable n-maximal Subgroups

Let G be a finite group and M _n (G) be the set of n-maximal subgroups of G, where n is an arbitrary given positive integer. Suppose that M _n (G) contains a nonidentity member and all members in M _n (G) are S-permutable in G. Then any of of the following conditions guarantees the supersolvability of G: (1) M _n (G) contains a nonidentity member whose order is not a prime; (2) all nonidentity members in M _n (G) are of prime order, and all cyclic members in M _n?1(G) of order 4 are S-permutable in G.     

Product irregularity strength of graphs

Consider a simple graph G with no isolated edges and at most one isolated vertex. A labeling w:E(G)→{1,2,…,m} is called product-irregular, if all product degrees pd_G(v)=∏_e∋vw(e) are distinct. The goal is to obtain a product-irregular labeling that minimizes the maximum label. This minimum value is called the product irregularity strength. The analogous concept of irregularity strength, with sums in place of products, has been introduced by Chartrand et al. and investigated by many authors.     

Retractions of split graphs and End-orthodox split graphs

A retraction f of a graph G is an edge-preserving mapping of G with f(v)=v for all v∈V(H), where H is the subgraph induced by the range of f. A graph G is called End-orthodox (End-regular) if its endomorphism monoid End X is orthodox (regular) in the semigroup sense. It is known that a graph is End-orthodox if it is End-regular and the composition of any two retractions is also a retraction. The retractions of split graphs are given and End-orthodox split graphs are characterized.     

A short and unified proof of Yu et al.?s two results on the eccentric distance sum

The eccentric distance sum (EDS) is a novel topological index that offers a vast potential for structure activity/property relationships. For a connected graph G, the eccentric distance sum is defined as ξd(G)=_∑v∈V(G)ecG(v)DG(v), where ecG(v) is the eccentricity of a vertex v in G and DG(v) is the sum of distances of all vertices in G from v. More recently, Yu et al. [G. Yu, L. Feng, A. Ili?, On the eccentric distance sum of trees and unicyclic graphs, J. Math. Anal. Appl. 375 (2011) 99-107] proved that for an n-vertex tree T, ξd(T)?4n²−9n+5, with equality holding if and only if T is the n-vertex star Sn, and for an n-vertex unicyclic graph G, ξd(G)?4n²−9n+1, with equality holding if and only if G is the graph obtained by adding an edge between two pendent vertices of n-vertex star. In this note, we give a short and unified proof of the above two results.     

Sharp bounds for the largest eigenvalue of the signless Laplacian of a graph

Let G be a simple connected graph with n vertices and m edges. Denote the degree of vertex v_i by d(v_i). The matrix Q(G)=D(G)+A(G) is called the signless Laplacian of G, where D(G)=diag(d(v₁),d(v₂),…,d(v_n)) and A(G) denote the diagonal matrix of vertex degrees and the adjacency matrix of G, respectively. Let q₁(G) be the largest eigenvalue of Q(G). In this paper, we first present two sharp upper bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G and give a new proving method on another sharp upper bound for q₁(G). Then we present three sharp lower bounds for q₁(G) involving the maximum degree and the minimum degree of the vertices of G. Moreover, we determine all extremal graphs which attain these sharp bounds.     

Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz

For a graph G, let χ(G) denote its chromatic number and σ(G) denote the order of the largest clique subdivision in G. Let H(n) be the maximum of χ(G)=σ(G) over all n-vertex graphs G. A famous conjecture of Hajós from 1961 states that σ(G) ≥ χ(G) for every graph G. That is, H(n)≤1 for all positive integers n. This conjecture was disproved by Catlin in 1979. Erd?s and Fajtlowicz further showed by considering a random graph that H(n)≥cn ^1/2/logn for some absolute constant c>0. In 1981 they conjectured that this bound is tight up to a constant factor in that there is some absolute constant C such that χ(G)=σ(G) ≤ Cn ^1/2/logn for all n-vertex graphs G. In this paper we prove the Erd?s-Fajtlowicz conjecture. The main ingredient in our proof, which might be of independent interest, is an estimate on the order of the largest clique subdivision which one can find in every graph on n vertices with independence number α.     

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.