Proof of the bandwidth conjecture of Bollobás and Komlós

In this paper we prove the following conjecture by Bollobás and Komlós: For every γ > 0 and integers r ≥ 1 and Δ, there exists β > 0 with the following property. If G is a sufficiently large graph with n vertices and minimum degree at least ((r ? 1)/r + γ)n and H is an r-chromatic graph with n vertices, bandwidth at most β n and maximum degree at most Δ, then G contains a copy of H.     

An implicit degree condition for relative length of long paths and cycles in graphs

For a graph G, we denote by p(G) and c(G) the number of vertices of a longest path and a longest cycle in G, respectively. For a vertex v in G, id(v) denotes the implicit degree of v. In this paper, we obtain that if G is a 2-connected graph on n vertices such that the implicit degree sum of any three independent vertices is at least n + 1, then either G contains a hamiltonian path, or c(G) ≥ p(G) ? 1.     

Minimum implicit degree condition restricted to claws for hamiltonian cycles

Let id(v) denote the implicit degree of a vertex v in a graph G. We define G to be implicit 1-heavy (implicit 2-heavy) if at least one (two) of the end vertices of each induced claw has (have) implicit degree at least n/2. In this paper, we prove that: (a) Let G be a 2-connected graph of order n ≥ 3. If G is implicit 2-heavy and |N(u) ∩ N(v)| ≥ 2 for every pair of vertices u and v with d(u, v) = 2 and max{id(u), id(v)} < n/2, then G is hamiltonian. (b) Let G be a 3-connected graph of order n ≥ 3. If G is implicit 1-heavy and |N(u) ∩ N(v)| ≥ 2 for each pair of vertices u and v with d(u, v) = 2 and max{id(u), id(v)} < n/2, then G is hamiltonian.     

Hamiltonian cycles in Dirac graphs

We prove that for any n-vertex Dirac graph (graph with minimum degree at least n/2) G=(V,E), the number, Ψ(G), of Hamiltonian cycles in G is at least

$exp_2 [2h(G) - n\log e - o(n)],$

where h(G)=maxΣ _e x _e log(1/x _e ), the maximum over x: E → ?⁺ satisfying Σ _e?υ x _e = 1 for each υ ∈ V, and log =log₂. (A second paper will show that this bound is tight up to the o(n).)

We also show that for any (Dirac) G of minimum degree at least d, h(G) ≥ (n/2) logd, so that Ψ(G) > (d/(e + o(1))) ⁿ . In particular, this says that for any Dirac G we have Ψ(G) > n!/(2 + o(1)) ⁿ , confirming a conjecture of G. Sárközy, Selkow, and Szemerédi which was the original motivation for this work.     

A sharp eigenvalue theorem for fractional elliptic equations

The invisibility graph I(X) of a set X ? R ^d is a (possibly infinite) graph whose vertices are the points of X and two vertices are connected by an edge if and only if the straight-line segment connecting the two corresponding points is not fully contained in X. We consider the following three parameters of a set X: the clique number ω(I(X)), the chromatic number χ(I(X)) and the convexity number γ(X), which is the minimum number of convex subsets of X that cover X.We settle a conjecture of Matou?ek and Valtr claiming that for every planar set X, γ(X) can be bounded in terms of χ(I(X)). As a part of the proof we show that a disc with n one-point holes near its boundary has χ(I(X)) ≥ log log(n) but ω(I(X)) = 3.We also find sets X in R⁵ with χ(X) = 2, but γ(X) arbitrarily large.     

A note on the independent domination number versus the domination number in bipartite graphs

Let γ(G) and i(G) be the domination number and the independent domination number of G, respectively. Rad and Volkmann posted a conjecture that i(G)/γ(G) ≤ Δ(G)/2 for any graph G, where Δ(G) is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than Δ(G)/2 are provided as well.     

Graphs with small diameter determined by their <Emphasis Type="Italic">D</Emphasis>-spectra

Let G be a connected graph with vertex set V(G) = {v₁, v₂,..., v _n }. The distance matrix D(G) = (d _ij )_n×n is the matrix indexed by the vertices of G, where d _ij denotes the distance between the vertices v _i and v _j . Suppose that λ₁(D) ≥ λ₂(D) ≥... ≥ λ _n (D) are the distance spectrum of G. The graph G is said to be determined by its D-spectrum if with respect to the distance matrix D(G), any graph having the same spectrum as G is isomorphic to G. We give the distance characteristic polynomial of some graphs with small diameter, and also prove that these graphs are determined by their D-spectra.     

Every graph is (2,3)-choosable

A total weighting of a graph G is a mapping ? that assigns to each element z ∈ V (G)∪E(G) a weight ?(z). A total weighting ? is proper if for any two adjacent vertices u and v, ∑ _e∈E(u) ?(e)+?(u)≠∑ _e∈E(v) ?(e)+?(v). This paper proves that if each edge e is given a set L(e) of 3 permissible weights, and each vertex v is given a set L(v) of 2 permissible weights, then G has a proper total weighting ? with ?(z) ∈ L(z) for each element z ∈ V (G)∪E(G).     

Neighbor sum distinguishing colorings of graphs with maximum average degree less than $$\tfrac{{37}} {{12}}$$

Let G be a graph and let its maximum degree and maximum average degree be denoted by Δ(G) and mad(G), respectively. A neighbor sum distinguishing k-edge colorings of graph G is a proper k-edge coloring of graph G such that, for any edge uv ∈ E(G), the sum of colors assigned on incident edges of u is different from the sum of colors assigned on incident edges of v. The smallest value of k in such a coloring of G is denoted by χ′_∑(G). Flandrin et al. proposed the following conjecture that χ′_∑ (G) ≤ Δ(G) + 2 for any connected graph with at least 3 vertices and G ≠ C₅. In this paper, we prove that the conjecture holds for a normal graph with mad(G) < \(\tfrac{{37}}{{12}}\) and Δ(G) ≥ 7.     

Neighborhood contraction in graphs

Let G be a graph and v be any vertex of G. Then the neighborhood contracted graphG_v of G, with respect to the vertex v, is the graph with vertex set V ? N(v), where two vertices u,w ∈ V ? N(v) are adjacent in G_v if either w = v and u is adjacent to any vertex of N(v) in G or u,w ? N[v] and u,w are adjacent in G. The properties of the neighborhood contracted graphs are discussed in this paper. The neighborhood contraction in some special class of graphs, the domination in a graph and the neighborhood contracted graphs are discussed in the paper.     

Some sufficient conditions for Hamiltonian property in terms of Wiener-type invariants

The Wiener-type invariants of a simple connected graph G = (V, E) can be expressed in terms of the quantities \(W_{f}=\sum_{\{u,v\}\subseteq V}f(d_{G}(u,v))\) for various choices of the function f(x), where d_G(u,v) is the distance between vertices u and v in G. In this paper, we give some sufficient conditions for a connected graph to be Hamiltonian, a connected graph to be traceable, and a connected bipartite graph to be Hamiltonian in terms of the Wiener-type invariants.     

On judicious bipartitions of graphs

For a positive integer m, let f(m) be the maximum value t such that any graph with m edges has a bipartite subgraph of size at least t, and let g(m) be the minimum value s such that for any graph G with m edges there exists a bipartition V (G)=V ₁?V ₂ such that G has at most s edges with both incident vertices in V _i . Alon proved that the limsup of \(f\left( m \right) - \left( {m/2 + \sqrt {m/8} } \right)\) tends to infinity as m tends to infinity, establishing a conjecture of Erd?s. Bollobás and Scott proposed the following judicious version of Erd?s' conjecture: the limsup of \(m/4 + \left( {\sqrt {m/32} - g(m)} \right)\) tends to infinity as m tends to infinity. In this paper, we confirm this conjecture. Moreover, we extend this conjecture to k-partitions for all even integers k. On the other hand, we generalize Alon's result to multi-partitions, which should be useful for generalizing the above Bollobás-Scott conjecture to k-partitions for odd integers k.     

On Eccentric Connectivity Index of Eccentric Graph of Regular Dendrimer

The eccentric connectivity index \(\xi ^c(G)\) of a connected graph G is defined as \(\xi ^c(G) =\sum _{v \in V(G)}{deg(v) e(v)},\) where deg(v) is the degree of vertex v and e(v) is the eccentricity of v. The eccentric graph, \(G_e\), of a graph G has the same set of vertices as G,  with two vertices u, v adjacent in \(G_e\) if and only if either u is an eccentric vertex of v or v is an eccentric vertex of u. In this paper, we obtain a formula for the eccentric connectivity index of the eccentric graph of a regular dendrimer. We also derive a formula for the eccentric connectivity index for the second iteration of eccentric graph of regular dendrimer.     

Characterization of the alternating groups by their order and one conjugacy class length

Let G be a finite group, and let N(G) be the set of conjugacy class sizes of G. By Thompson’s conjecture, if L is a finite non-abelian simple group, G is a finite group with a trivial center, and N(G) = N(L), then L and G are isomorphic. Recently, Chen et al. contributed interestingly to Thompson’s conjecture under a weak condition. They only used the group order and one or two special conjugacy class sizes of simple groups and characterized successfully sporadic simple groups (see Li’s PhD dissertation). In this article, we investigate validity of Thompson’s conjecture under a weak condition for the alternating groups of degrees p+1 and p+2, where p is a prime number. This work implies that Thompson’s conjecture holds for the alternating groups of degree p + 1 and p + 2.     

On the Automorphism Group of a Smooth Schubert Variety

Let G be a simple algebraic group of adjoint type over the field \(\mathbb {C}\) of complex numbers. Let B be a Borel subgroup of G containing a maximal torus T of G. Let w be an element of the Weyl group W and let X(w) be the Schubert variety in G/B corresponding to w. Let α ₀ denote the highest root of G with respect to T and B. Let P be the stabiliser of X(w) in G. In this paper, we prove that if G is simply laced and X(w) is smooth, then the connected component of the automorphism group of X(w) containing the identity automorphism equals P if and only if w ^?1(α ₀) is a negative root (see Theorem 4.2). We prove a partial result in the non simply laced case (see Theorem 6.6).     

A note on the Engelking-Karłowicz theorem

We investigate the chromatic number of infinite graphs whose definition is motivated by the theorem of Engelking and Kar?owicz (in [?]). In these graphs, the vertices are subsets of an ordinal, and two subsets X and Y are connected iff for some a ∈ X ∩ Y the order-type of a ∩ X is different from that of a ∩ Y.In addition to the chromatic number x(G) of these graphs we study χ _κ (G), the κ-chromatic number, which is the least cardinal µ with a decomposition of the vertices into µ classes none of which contains a κ-complete subgraph.     

Coloring number and on-line Ramsey theory for graphs and hypergraphs

Let c,s,t be positive integers. The (c,s,t)-Ramsey game is played by Builder and Painter. Play begins with an s-uniform hypergraph G ₀=(V,E ₀), where E ₀=Ø and V is determined by Builder. On the ith round Builder constructs a new edge e _i (distinct from previous edges) and sets G _i =(V,E _i ), where E _i =E _i?1∪{e _i }. Painter responds by coloring e _i with one of c colors. Builder wins if Painter eventually creates a monochromatic copy of K _s ^t , the complete s-uniform hypergraph on t vertices; otherwise Painter wins when she has colored all possible edges.We extend the definition of coloring number to hypergraphs so that χ(G)≤col(G) for any hypergraph G and then show that Builder can win (c,s,t)-Ramsey game while building a hypergraph with coloring number at most col(K _s ^t ). An important step in the proof is the analysis of an auxiliary survival game played by Presenter and Chooser. The (p,s,t)-survival game begins with an s-uniform hypergraph H ₀ = (V,Ø) with an arbitrary finite number of vertices and no edges. Let H _i?1=(V _i?1,E _i?1) be the hypergraph constructed in the first i ? 1 rounds. On the i-th round Presenter plays by presenting a p-subset P _i ?V _i?1 and Chooser responds by choosing an s-subset X _i ?P _i . The vertices in P _i ? X _i are discarded and the edge X _i added to E _i?1 to form E _i . Presenter wins the survival game if H _i contains a copy of K _s ^t for some i. We show that for positive integers p,s,t with s≤p, Presenter has a winning strategy.     

An Ore-Type Theorem on Hamiltonian Square Cycles

The kth power of a cycle C is the graph obtained from C by joining every pair of vertices with distance at most k on C. The second power of a cycle is called a square cycle. Pósa conjectured that every graph with minimum degree at least 2n/3 contains a hamiltonian square cycle. Later, Seymour proposed a more general conjecture that if G is a graph with minimum degree at least (kn)/(k + 1), then G contains the kth power of a hamiltonian cycle. Here we prove an Ore-type version of Pósa’s conjecture that if G is a graph in which deg(u) + deg(v) ≥ 4n/3 ? 1/3 for all non-adjacent vertices u and v, then for sufficiently large n, G contains a hamiltonian square cycle unless its minimum degree is exactly n/3 + 2 or n/3 + 5/3. A consequence of this result is an Ore-type analogue of a theorem of Aigner and Brandt.     

On <Emphasis Type="Italic">g</Emphasis><Subscript><Emphasis Type="Italic">c</Emphasis></Subscript>-colorings of nearly bipartite graphs

Let G be a simple graph, let d(v) denote the degree of a vertex v and let g be a nonnegative integer function on V (G) with 0 ≤ g(v) ≤ d(v) for each vertex v ∈ V (G). A g _c -coloring of G is an edge coloring such that for each vertex v ∈ V (G) and each color c, there are at least g(v) edges colored c incident with v. The g _c -chromatic index of G, denoted by χ′g _c (G), is the maximum number of colors such that a gc-coloring of G exists. Any simple graph G has the g _c -chromatic index equal to δ _g (G) or δ _g (G) ? 1, where \({\delta _g}\left( G \right) = \mathop {\min }\limits_{v \in V\left( G \right)} \left\lfloor {d\left( v \right)/g\left( v \right)} \right\rfloor \). A graph G is nearly bipartite, if G is not bipartite, but there is a vertex u ∈ V (G) such that G ? u is a bipartite graph. We give some new sufficient conditions for a nearly bipartite graph G to have χ′g _c (G) = δ _g (G). Our results generalize some previous results due to Wang et al. in 2006 and Li and Liu in 2011.     

On total colorings of some special 1-planar graphs

A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. In this paper, we verify the total coloring conjecture for every 1-planar graph G if either Δ(G) ≥ 9 and g(G) ≥ 4, or Δ(G) ≥ 7 and g(G) ≥ 5, where Δ(G) is the maximum degree of G and g(G) is the girth of G.