A variation of a conjecture due to Erdös and Sós

Erdoes and Soes conjectured in 1963 that every graph G on n vertices with edge number e（G） 〉 1/2（k - 1）n contains every tree T with k edges as a subgraph. In this paper, we consider a variation of the above conjecture, that is, for n 〉 9/ 2k^2 ＋ 37/2＋ 14 and every graph G on n vertices with e（G） 〉 1/2 （k- 1）n, we prove that there exists a graph G＇ on n vertices having the same degree sequence as G and containing every tree T with k edges as a subgraph.     

Edge clique covering sum of graphs

The edge clique cover sum number (resp. edge clique partition sum number) of a graph G, denoted by scc(G) (resp. scp(G)), is defined as the smallest integer k for which there exists a collection of complete subgraphs of G, covering (resp. partitioning) all edges of G such that the sum of sizes of the cliques is at most k. By definition, scc(G) \({\leqq}\) scp(G). Also, it is known that for every graph G on n vertices, scp(G) \({\leqq n^{2}/2}\). In this paper, among some other results, we improve this bound for scc(G). In particular, we prove that if G is a graph on n vertices with no isolated vertex and the maximum degree of the complement of G is d ? 1, for some integer d, then scc(G) \({\leqq cnd\left\lceil\log \left(({n-1})/(d-1)\right)\right\rceil}\), where c is a constant. Moreover, we conjecture that this bound is best possible up to a constant factor. Using a well-known result by Bollobás on set systems, we prove that this conjecture is true at least for d = 2. Finally, we give an interpretation of this conjecture as an interesting set system problem which can be viewed as a multipartite generalization of Bollobás’ two families theorem.     

Invariant subsets of scattered trees and the tree alternative property of Bonato and Tardif

A tree is scattered if it does not contain a subdivision of the complete binary tree as a subtree. We show that every scattered tree contains a vertex, an edge, or a set of at most two ends preserved by every embedding of T. This extends results of Halin, Polat and Sabidussi. Calling two trees equimorphic if each embeds in the other, we then prove that either every tree that is equimorphic to a scattered tree T is isomorphic to T, or there are infinitely many pairwise non-isomorphic trees which are equimorphic to T. This proves the tree alternative conjecture of Bonato and Tardif for scattered trees, and a conjecture of Tyomkyn for locally finite scattered trees.     

Note: A conjecture on partitions of groups

We conjecture that every infinite group G can be partitioned into countably many cells \(G = \bigcup\limits_{n \in \omega } {A_n }\) such that cov(A _n A _n ^?1 ) = |G| for each n ∈ ω Here cov(A) = min{|X|: X} ? G, G = X A}. We confirm this conjecture for each group of regular cardinality and for some groups (in particular, Abelian) of an arbitrary cardinality.     

Properly discontinuous group actions on affine homogeneous spaces

Let G be a real algebraic group, H ≤ G an algebraic subgroup containing a maximal reductive subgroup of G, and Γ a subgroup of G acting on G/H by left translations. We conjecture that Γ is virtually solvable provided its action on G/H is properly discontinuous and ΓG/H is compact, and we confirm this conjecture when G does not contain simple algebraic subgroups of rank ≥2. If the action of Γ on G/H (which is isomorphic to an affine linear space Aⁿ) is linear, our conjecture coincides with the Auslander conjecture. We prove the Auslander conjecture for n ≤ 5.     

Peixoto graph of Morse-Smale diffeomorphisms on manifolds of dimension greater than three

Let M ⁿ be a closed orientable manifold of dimension greater than three and G ₁(M ⁿ ) be the class of orientation-preserving Morse-Smale diffeomorphisms on M ⁿ such that the set of unstable separatrices of every f ∈ G ₁(M ⁿ ) is one-dimensional and does not contain heteroclinic orbits. We show that the Peixoto graph is a complete invariant of topological conjugacy in G ₁(M ⁿ ).     

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.     

Chromatic number and subtrees of graphs

Let G and H be two graphs. We say that G induces H if G has an induced subgraph isomorphic to H: A. Gyárfás and D. Sumner, independently, conjectured that, for every tree T. there exists a function f _T ; called binding function, depending only on T with the property that every graph G with chromatic number f _T (ω(G)) induces T. A. Gyárfás, E. Szemerédi and Z. Tuza confirmed the conjecture for all trees of radius two on triangle-free graphs, and H. Kierstead and S. Penrice generalized the approach and the conclusion of A. Gyárfás et al. onto general graphs. A. Scott proved an interesting topological version of this conjecture asserting that for every integer k and every tree T of radius r, every graph G with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(14 ^r-1(r - 1)!) times. We extend the approach of A. Gyárfás and present a binding function for trees obtained by identifying one end of a path and the center of a star. We also improve A. Scott's upper bound by modifying his subtree structure and partition technique, and show that for every integer k and every tree T of radius r, every graph with ω(G) ? k and sufficient large chromatic number induces a subdivision of T of which each edge is subdivided at most O(6 ^r?2) times.     

Note on a conjecture for the sum of signless Laplacian eigenvalues

For a simple graph G on n vertices and an integer k with 1 ? k ? n, denote by \(\mathcal{S}^+_k\) (G) the sum of k largest signless Laplacian eigenvalues of G. It was conjectured that \(\mathcal{S}^+_k(G)\leqslant{e}(G)+(^{k+1}_{\;\;2})\) (G) ? e(G) + (k+1 2), where e(G) is the number of edges of G. This conjecture has been proved to be true for all graphs when k ∈ {1, 2, n ? 1, n}, and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all k). In this note, this conjecture is proved to be true for all graphs when k = n ? 2, and for some new classes of graphs.     

Judicious bisection of hypergraphs

Judicious bisection of hypergraphs asks for a balanced bipartition of the vertex set that optimizes several quantities simultaneously.In this paper,we prove that if G is a hypergraph with n vertices and m_i edges of size i for i=1,2,...,k,then G admits a bisection in which each vertex class spans at most(m_1)/2+1/4m_2+…+(1/(2~k)+m_k+o(m_1+…+m_k) edges,where G is dense enough or △(G)= o(n) but has no isolated vertex,which turns out to be a bisection version of a conjecture proposed by Bollobas and Scott.     

Generation of a finite group with Hall maximal subgroups by a pair of conjugate elements

For a finite group G, the set of all prime divisors of |G| is denoted by π(G). P. Shumyatsky introduced the following conjecture, which was included in the “Kourovka Notebook” as Question 17.125: a finite group G always contains a pair of conjugate elements a and b such that π(G) = π(〈a, b〉). Denote by \(\mathfrak{Y}\) the class of all finite groups G such that π(H) ≠ π(G) for every maximal subgroup H in G. Shumyatsky’s conjecture is equivalent to the following conjecture: every group from \(\mathfrak{Y}\) is generated by two conjugate elements. Let \(\mathfrak{V}\) be the class of all finite groups in which every maximal subgroup is a Hall subgroup. It is clear that \(\mathfrak{V} \subseteq \mathfrak{Y}\). We prove that every group from \(\mathfrak{V}\) is generated by two conjugate elements. Thus, Shumyatsky’s conjecture is partially supported. In addition, we study some properties of a smallest order counterexample to Shumyatsky’s conjecture.     

Uniquely Tree-saturated Graphs

Let H be a graph. A graph G is uniquely H-saturated if G contains no subgraph isomorphic to H, but for every edge e in the complement of G (i.e., for each “nonedge” of G), \(G+e\) contains exactly one subgraph isomorphic to H. The double star \(D_{s,t}\) is the graph formed by beginning with \(K_2\) and adding \(s+t\) new vertices, making s of these adjacent to one endpoint of the \(K_2\) and the other t adjacent to the other endpoint; \(D_{s,s}\) is a balanced double star. Our main result is that the trees T for which there exist an infinite number of uniquely T-saturated graphs are precisely the balanced double stars. In addition we completely characterize uniquely tree-saturated graphs in the case where the tree is a star \(K_{1,t} = D_{0, t-1}\). We show that if T is a double star, then there exists a nontrivial uniquely T-saturated graph. We conjecture that the converse holds; we verify this conjecture for all trees of order at most 6. We conclude by giving some open problems.     

On balanced colorings of the <Emphasis Type="Italic">n</Emphasis>-cube

A 2-coloring of the n-cube in the n-dimensional Euclidean space can be considered as an assignment of weights of 1 or 0 to the vertices. Such a colored n-cube is said to be balanced if its center of mass coincides with its geometric center. Let B _n,2k be the number of balanced 2-colorings of the n-cube with 2k vertices having weight 1. Palmer, Read, and Robinson conjectured that for n≥1, the sequence \(\{B_{n,2k}\}_{k=0,1,\ldots,2^{n-1}}\) is symmetric and unimodal. We give a proof of this conjecture. We also propose a conjecture on the log-concavity of B _n,2k for fixed k, and by probabilistic method we show that it holds when n is sufficiently large.     

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.     

Conditional connectivity of bubble sort graphs

A subset F ? V (G) is called an R ^k -vertex-cut of a graph G if G ? F is disconnected and each vertex of G ? F has at least k neighbors in G ? F. The R ^k -vertex-connectivity of G, denoted by κ ^k (G), is the cardinality of a minimum R ^k -vertex-cut of G. Let B _n be the bubble sort graph of dimension n. It is known that κ _k (B _n ) = 2 ^k (n ? k ? 1) for n ≥ 2k and k = 1, 2. In this paper, we prove it for k = 3 and conjecture that it is true for all k ∈ N. We also prove that the connectivity cannot be more than conjectured.     

On eigenvalues of Seidel matrices and Haemers’ conjecture

For a graph G, let S(G) be the Seidel matrix of G and \({\theta }_1(G),\ldots ,{\theta }_n(G)\) be the eigenvalues of S(G). The Seidel energy of G is defined as \(|{\theta }_1(G)|+\cdots +|{\theta }_n(G)|\). Willem Haemers conjectured that the Seidel energy of any graph with n vertices is at least \(2n-2\), the Seidel energy of the complete graph with n vertices. Motivated by this conjecture, we prove that for any \(\alpha \) with \(0<\alpha <2,|{\theta }_1(G)|^\alpha +\cdots +|{\theta }_n(G)|^\alpha \geqslant (n-1)^\alpha +n-1\) if and only if \(|\hbox {det}\,S(G)|\geqslant n-1\). This, in particular, implies the Haemers’ conjecture for all graphs G with \(|\hbox {det}\,S(G)|\geqslant n-1\). A computation on the fraction of graphs with \(|\hbox {det}\,S(G)|<n-1\) is reported. Motivated by that, we conjecture that almost all graphs G of order n satisfy \(|\hbox {det}\,S(G)|\geqslant n-1\). In connection with this conjecture, we note that almost all graphs of order n have a Seidel energy of order \(\Theta (n^{3/2})\). Finally, we prove that self-complementary graphs G of order \(n\equiv 1\pmod 4\) have \(\det S(G)=0\).     

Some Triangulated Surfaces without Balanced Splitting

Let G be the graph of a triangulated surface \(\varSigma \) of genus \(g\ge 2\). A cycle of G is splitting if it cuts \(\varSigma \) into two components, neither of which is homeomorphic to a disk. A splitting cycle has type k if the corresponding components have genera k and \(g-k\). It was conjectured that G contains a splitting cycle (Barnette 1982). We confirm this conjecture for an infinite family of triangulations by complete graphs but give counter-examples to a stronger conjecture (Mohar and Thomassen in Graphs on surfaces. Johns Hopkins studies in the mathematical sciences. Johns Hopkins University Press, Baltimore, 2001) claiming that G should contain splitting cycles of every possible type.     

On a new property of <Emphasis Type="Italic">n</Emphasis>-poised and <Emphasis Type="Italic">G</Emphasis><Emphasis Type="Italic">C</Emphasis><Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> sets

In this paper we consider n-poised planar node sets, as well as more special ones, called G C _n sets. For the latter sets each n-fundamental polynomial is a product of n linear factors as it always holds in the univariate case. A line ? is called k-node line for a node set \(\mathcal X\) if it passes through exactly k nodes. An (n + 1)-node line is called maximal line. In 1982 M. Gasca and J. I. Maeztu conjectured that every G C _n set possesses necessarily a maximal line. Till now the conjecture is confirmed to be true for n ≤ 5. It is well-known that any maximal line M of \(\mathcal X\) is used by each node in \(\mathcal X\setminus M, \)meaning that it is a factor of the fundamental polynomial. In this paper we prove, in particular, that if the Gasca-Maeztu conjecture is true then any n-node line of G C _n set \(\mathcal {X}\) is used either by exactly \(\binom {n}{2}\) nodes or by exactly \(\binom {n-1}{2}\) nodes. We prove also similar statements concerning n-node or (n ? 1)-node lines in more general n-poised sets. This is a new phenomenon in n-poised and G C _n sets. At the end we present a conjecture concerning any k-node line.     

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.     

Peckness of Edge Posets

For any graded poset P, we define a new graded poset, ??(P), whose elements are the edges in the Hasse diagram of P. For any group G acting on the boolean algebra B _n in a rank-preserving fashion we conjecture that ??(B _n /G) is Peck. We prove that the conjecture holds for “common cover transitive” actions. We give some infinite families of common cover transitive actions and show that the common cover transitive actions are closed under direct and semidirect products.