Connected size Ramsey number for matchings vs. small stars or cycles

The notation \(F\rightarrow (G,H)\) means that if the edges of F are colored red and blue, then the red subgraph contains a copy of G or the blue subgraph contains a copy of H. The connected size Ramsey number \(\hat{r}_c(G,H)\) of graphs G and H is the minimum size of a connected graph F satisfying \(F\rightarrow (G,H)\). For \(m \ge 2,\) the graph consisting of m independent edges is called a matching and is denoted by \(mK_2\). In 1981, Erdös and Faudree determined the size Ramsey numbers for the pair \((mK_2, K_{1,t})\). They showed that the disconnected graph \(mK_{1,t} \rightarrow (mK_2,K_{1,t})\) for \( t,m \ge 1\). In this paper, we will determine the connected size Ramsey number \(\hat{r}_c(nK_2, K_{1,3})\) for \(n\ge 2\) and \(\hat{r}_c(3K_2, C_4)\). We also derive an upper bound of the connected size Ramsey number \(\hat{r}_c(nK_2, C_4),\) for \(n\ge 4\).     

Edge Roman Domination on Graphs

An edge Roman dominating function of a graph G is a function \(f:E(G) \rightarrow \{0,1,2\}\) satisfying the condition that every edge e with \(f(e)=0\) is adjacent to some edge \(e'\) with \(f(e')=2\). The edge Roman domination number of G, denoted by \(\gamma '_R(G)\), is the minimum weight \(w(f) = \sum _{e\in E(G)} f(e)\) of an edge Roman dominating function f of G. This paper disproves a conjecture of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad stating that if G is a graph of maximum degree \(\Delta \) on n vertices, then \(\gamma _R'(G) \le \lceil \frac{\Delta }{\Delta +1} n \rceil \). While the counterexamples having the edge Roman domination numbers \(\frac{2\Delta -2}{2\Delta -1} n\), we prove that \(\frac{2\Delta -2}{2\Delta -1} n + \frac{2}{2\Delta -1}\) is an upper bound for connected graphs. Furthermore, we provide an upper bound for the edge Roman domination number of k-degenerate graphs, which generalizes results of Akbari, Ehsani, Ghajar, Jalaly Khalilabadi and Sadeghian Sadeghabad. We also prove a sharp upper bound for subcubic graphs. In addition, we prove that the edge Roman domination numbers of planar graphs on n vertices is at most \(\frac{6}{7}n\), which confirms a conjecture of Akbari and Qajar. We also show an upper bound for graphs of girth at least five that is 2-cell embeddable in surfaces of small genus. Finally, we prove an upper bound for graphs that do not contain \(K_{2,3}\) as a subdivision, which generalizes a result of Akbari and Qajar on outerplanar graphs.     

Hadwiger’s conjecture for uncountable graphs

We consider the infinite form of Hadwiger’s conjecture. We give a(n apparently novel) proof of Halin’s 1967 theorem stating that every graph X with coloring number \(>\kappa \) (specifically with chromatic number \(>\kappa \)) contains a subdivision of \(K_\kappa \). We also prove that there is a graph of cardinality \(2^\kappa \) and chromatic number \(\kappa ^+\) which does not contain \(K_{\kappa ^+}\) as a minor. Further, it is consistent that every graph of size and chromatic number \(\aleph _1\) contains a subdivision of \(K_{\aleph _1}\).     

2-Arc-transitive cyclic covers of $$K_{n,n}$$

In this paper, a complete classification is achieved of all the regular covers of the complete bipartite graphs \(K_{n,n}\) with cyclic covering transformation group, whose fibre-preserving automorphism group acts 2-arc-transitively. All these covers consist of one threefold covers of \(K_{6,6}\), one twofold cover of \(K_{12, 12}\) and one infinite family X(r, p) of p-fold covers of \(K_{p^r,p^r}\) with p a prime and r an integer such that \(p^r\ge 3\). This infinite family X(r, p) can be derived by a very simple and nice voltage assignment f as follows: \(X(r, p)=K_{p^r, p^r}\times _f \mathbb {Z}_p\), where \(K_{p^r, p^r}\) is a complete bipartite graph with the bipartition \(V=\{ \alpha \bigm |\alpha \in V(r,p)\}\cup \{ \alpha '\bigm |\alpha \in V(r,p)\}\) for the r-dimensional vector space V(r, p) over the field of order p and \(f_{\alpha ,\beta '}=\sum _{i=1}^ra_ib_i,\,\, \mathrm{for\,\,all}\,\,\alpha =(a_i)_r, \beta =(b_i)_r\in V(r,p)\).     

Decomposition of Complete Bipartite Graphs into Cycles of Distinct Even Lengths

Let \(K_{n,n}\) be the complete bipartite graph with two parts of equal size n. In this paper, it is shown that depending on whether n is even or odd, \(K_{n,n}\) or \(K_{n,n}-I\), where I is a 1-factor of \(K_{n,n}\), can be decomposed into cycles of distinct even lengths for any integer \(n \ge 2\) with the exception of \(n = 4\).     

Calabi-Yau manifolds with isolated conical singularities

Let \(X\) be a complex projective variety with only canonical singularities and with trivial canonical bundle. Let \(L\) be an ample line bundle on \(X\). Assume that the pair \((X,L)\) is the flat limit of a family of smooth polarized Calabi-Yau manifolds. Assume that for each singular point \(x \in X\) there exist a Kähler-Einstein Fano manifold \(Z\) and a positive integer \(q\) dividing \(K_{Z}\) such that \(-\frac{1}{q}K_{Z}\) is very ample and such that the germ \((X,x)\) is locally analytically isomorphic to a neighborhood of the vertex of the blow-down of the zero section of \(\frac{1}{q}K_{Z}\). We prove that up to biholomorphism, the unique weak Ricci-flat Kähler metric representing \(2\pi c_{1}(L)\) on \(X\) is asymptotic at a polynomial rate near \(x\) to the natural Ricci-flat Kähler cone metric on \(\frac{1}{q}K_{Z}\) constructed using the Calabi ansatz. In particular, our result applies if \((X, \mathcal{O}(1))\) is a nodal quintic threefold in \(\mathbf {P}^{4}\). This provides the first known examples of compact Ricci-flat manifolds with non-orbifold isolated conical singularities.     

On Star–Wheel Ramsey Numbers

For two given graphs \(G_1\) and \(G_2\), the Ramsey number \(R(G_1,G_2)\) is the least integer r such that for every graph G on r vertices, either G contains a \(G_1\) or \(\overline{G}\) contains a \(G_2\). In this note, we determined the Ramsey number \(R(K_{1,n},W_m)\) for even m with \(n+2\le m\le 2n-2\), where \(W_m\) is the wheel on \(m+1\) vertices, i.e., the graph obtained from a cycle \(C_m\) by adding a vertex v adjacent to all vertices of the \(C_m\).     

Cliques in $$C_4$$-free graphs of large minimum degree

A graph G is called \(C_4\)-free if it does not contain the cycle \(C_4\) as an induced subgraph. Hubenko, Solymosi and the first author proved (answering a question of Erd?s) a peculiar property of \(C_4\)-free graphs: \(C_4\)-free graphs with n vertices and average degree at least cn contain a complete subgraph (clique) of size at least \(c'n\) (with \(c'= 0.1c^2\)). We prove here better bounds \(\big ({c^2n\over 2+c}\) in general and \((c-1/3)n\) when \( c \le 0.733\big )\) from the stronger assumption that the \(C_4\)-free graphs have minimum degree at least cn. Our main result is a theorem for regular graphs, conjectured in the paper mentioned above: 2k-regular \(C_4\)-free graphs on \(4k+1\) vertices contain a clique of size \(k+1\). This is the best possible as shown by the kth power of the cycle \(C_{4k+1}\).     

Random Walks in the Hyperbolic Plane and the Minkowski Question Mark Function

Consider \(G=SL_2(\mathbb {Z})/\{\pm I\}\) acting on the complex upper half plane H by \(h_M(z)=\frac{az\,+\,b}{cz\,+\,d}\) for \(M \in G\). Let \(D=\{z \in H: |z|\ge 1, |\mathfrak {R}(z)|\le 1/2\}\). We consider the set \({\mathcal {E}} \subset G\) with the nine elements M, different from the identity, such that \(\mathrm{tr\,}(MM^T)\le 3\). We equip the tiling of H defined by \(\mathbb {D}=\{h_M(D){:}\, M \in G\}\) with a graph structure where the neighbours are defined by \(h_M(D) \cap h_{M'}(D) \ne \emptyset \), equivalently \(M^{-1}M' \in {\mathcal {E}}\). The present paper studies several Markov chains related to the above structure. We show that the simple random walk on the above graph converges a.s. to a point X of the real line with the same distribution of \(S_2 W^{S_1}\), where \(S_1,S_2,W\) are independent with \(\Pr (S_i=\pm 1)=1/2\) and where W is valued in (0, 1) with distribution \(\Pr (W<w)=\mathbf ? (w)\). Here \(\mathbf ? \) is the Minkowski function. If \(K_1, K_2, \ldots \) are i.i.d with distribution \(\Pr (K_i=n)= 1/2^n\) for \(n=1,2,\ldots \), then \(W= \frac{1}{K_1+\frac{1}{K_2+\ldots }}\): this known result (Isola in Appl Math 5:1067–1090, 2014) is derived again here.     

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.     

Generalized Correspondence Analysis for Three-Valued Logics

Correspondence analysis is Kooi and Tamminga’s universal approach which generates in one go sound and complete natural deduction systems with independent inference rules for tabular extensions of many-valued functionally incomplete logics. Originally, this method was applied to Asenjo–Priest’s paraconsistent logic of paradox LP. As a result, one has natural deduction systems for all the logics obtainable from the basic three-valued connectives of LP (which is built in the \( \{\vee ,\wedge ,\lnot \} \)-language) by the addition of unary and binary connectives. Tamminga has also applied this technique to the paracomplete analogue of LP, strong Kleene logic \( \mathbf K_3 \). In this paper, we generalize these results for the negative fragments of LP and \( \mathbf K_3 \), respectively. Thus, the method of correspondence analysis works for the logics which have the same negations as LP or \( \mathbf K_3 \), but either have different conjunctions or disjunctions or even don’t have them as well at all. Besides, we show that correspondence analyses for the negative fragments of \( \mathbf K_3 \) and LP, respectively, are also suitable without any changes for the negative fragments of Heyting’s logic \( \mathbf G_3 \) and its dual \( \mathbf DG_3 \) (which have different interpretations of negation than \( \mathbf K_3 \) and LP).     

Structural Properties of Word Representable Graphs

Given a word \(w=w_1w_2\cdots w_n\) of length n over an ordered alphabet \(\Sigma _k\), we construct a graph \(G(w)=(V(w), E(w))\) such that V(w) has n vertices labeled \(1, 2,\ldots , n\) and for \(i, j \in V(w)\), \((i, j) \in E(w)\) if and only if \(w_iw_j\) is a scattered subword of w of the form \(a_{t}a_{t+1}\), \(a_t \in \Sigma _k\), for some \(1 \le t \le k-1\) with the ordering \(a_t<a_{t+1}\). A graph is said to be Parikh word representable if there exists a word w over \(\Sigma _k\) such that \(G=G(w)\). In this paper we characterize all Parikh word representable graphs over the binary alphabet in terms of chordal bipartite graphs. It is well known that the graph isomorphism (GI) problem for chordal bipartite graph is GI complete. The GI problem for a subclass of (6, 2) chordal bipartite graphs has been addressed. The notion of graph powers is a well studied topic in graph theory and its applications. We also investigate a bipartite analogue of graph powers of Parikh word representable graphs. In fact we show that for G(w), \(G(w)^{[3]}\) is a complete bipartite graph, for any word w over binary alphabet.     

The graphs with exactly two distance eigenvalues different from $$$$ and $$-3$$-3

In this paper, we completely characterize the graphs with third largest distance eigenvalue at most \(-1\) and smallest distance eigenvalue at least \(-3\). In particular, we determine all graphs whose distance matrices have exactly two eigenvalues (counting multiplicity) different from \(-1\) and \(-3\). It turns out that such graphs consist of three infinite classes, and all of them are determined by their distance spectra. We also show that the friendship graph is determined by its distance spectrum.     

A finite spectral representation of the partition function

Let \(E_{/\mathbb {Q}}\!\) be an elliptic curve, \(p>3\) a good ordinary prime for E, and \(K_\infty \) a p-adic Lie extension of a number field k. Under some standard hypotheses, we study the asymptotic growth in both the Mordell–Weil rank and Shafarevich–Tate group for E over a tower of extensions \(K_n/k\) inside \(K_\infty \); we obtain lower bounds on the former, and upper bounds on the latter’s size.     

2-Domination number of generalized Petersen graphs

Let \(G=(V,E)\) be a graph. A subset \(S\subseteq V\) is a k-dominating set of G if each vertex in \(V-S\) is adjacent to at least k vertices in S. The k-domination number of G is the cardinality of the smallest k-dominating set of G. In this paper, we shall prove that the 2-domination number of generalized Petersen graphs \(P(5k+1, 2)\) and \(P(5k+2, 2)\), for \(k>0\), is \(4k+2\) and \(4k+3\), respectively. This proves two conjectures due to Cheng (Ph.D. thesis, National Chiao Tung University, 2013). Moreover, we determine the exact 2-domination number of generalized Petersen graphs P(2k, k) and \(P(5k+4,3)\). Furthermore, we give a good lower and upper bounds on the 2-domination number of generalized Petersen graphs \(P(5k+1, 3), P(5k+2,3)\) and \(P(5k+3, 3).\)     

Dominating Cycles and Forbidden Pairs Containing $$P_{5}$$

A cycle C in a graph G is dominating if every edge of G is incident with at least one vertex of C. For a set \(\mathcal {H}\) of connected graphs, a graph G is said to be \(\mathcal {H}\)-free if G does not contain any member of \(\mathcal {H}\) as an induced subgraph. When \(|\mathcal {H}| = 2, \mathcal {H}\) is called a forbidden pair. In this paper, we investigate the characterization of the class of the forbidden pairs guaranteeing the existence of a dominating cycle and show the following two results: (i) Every 2-connected \(\{P_{5}, K_{4}^{-}\}\)-free graph contains a longest cycle which is a dominating cycle. (ii) Every 2-connected \(\{P_{5}, W^{*}\}\)-free graph contains a longest cycle which is a dominating cycle. Here \(P_{5}\) is the path of order \(5, K_{4}^{-}\) is the graph obtained from the complete graph of order 4 by removing one edge, and \(W^{*}\) is the graph obtained from two triangles and an edge by identifying one vertex in each.     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

Remarks on curvature dimension conditions on graphs

We show a connection between the \(CDE'\) inequality introduced in Horn et al. (Volume doubling, Poincaré inequality and Gaussian heat kernel estimate for nonnegative curvature graphs. arXiv:1411.5087v2, 2014) and the \(CD\psi \) inequality established in Münch (Li–Yau inequality on finite graphs via non-linear curvature dimension conditions. arXiv:1412.3340v1, 2014). In particular, we introduce a \(CD_\psi ^\varphi \) inequality as a slight generalization of \(CD\psi \) which turns out to be equivalent to \(CDE'\) with appropriate choices of \(\varphi \) and \(\psi \). We use this to prove that the \(CDE'\) inequality implies the classical CD inequality on graphs, and that the \(CDE'\) inequality with curvature bound zero holds on Ricci-flat graphs.     

Integral Cayley graphs over dihedral groups

In this paper, we give a necessary and sufficient condition for the integrality of Cayley graphs over the dihedral group \(D_n=\langle a,b\mid a^n=b^2=1,bab=a^{-1}\rangle \). Moreover, we also obtain some simple sufficient conditions for the integrality of Cayley graphs over \(D_n\) in terms of the Boolean algebra of \(\langle a\rangle \), from which we find infinite classes of integral Cayley graphs over \(D_n\). In particular, we completely determine all integral Cayley graphs over the dihedral group \(D_p\) for a prime p.     

Homomorphism reductions on Polish groups

In an earlier paper, we introduced the following pre-order on the subgroups of a given Polish group: if G is a Polish group and \(H,L \subseteq G\) are subgroups, we say H is homomorphism reducible to L iff there is a continuous group homomorphism \(\varphi : G \rightarrow G\) such that \(H = \varphi ^{-1} (L)\). We previously showed that there is a \(K_\sigma \) subgroup L of the countable power of any locally compact Polish group G such that every \(K_\sigma \) subgroup of \(G^\omega \) is homomorphism reducible to L. In the present work, we show that this fails in the countable power of the group of increasing homeomorphisms of the unit interval.