Anti-Ramsey Numbers of Graphs with Small Connected Components

The anti-Ramsey number, AR(n, G), for a graph G and an integer \(n\ge |V(G)|\), is defined to be the minimal integer r such that in any edge-colouring of \(K_n\) by at least r colours there is a multicoloured copy of G, namely, a copy of G that each of its edges has a distinct colour. In this paper we determine, for large enough \(n,\, AR(n,L\cup tP_2)\) and \(AR(n,L\cup kP_3)\) for any large enough t and k, and a graph L satisfying some conditions. Consequently, we determine AR(n, G), for large enough n, where G is \(P_3\cup tP_2\) for any \(t\ge 3,\, P_4\cup tP_2\) and \(C_3\cup tP_2\) for any \(t\ge 2,\, kP_3\) for any \(k\ge 3,\, tP_2\cup kP_3\) for any \(t\ge 1,\, k\ge 2\), and \(P_{t+1}\cup kP_3\) for any \(t\ge 3,\, k\ge 1\). Furthermore, we obtain upper and lower bounds for AR(n, G), for large enough n, where G is \(P_{k+1}\cup tP_2\) and \(C_k\cup tP_2\) for any \(k\ge 4,\, t\ge 1\).     

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.     

Largest independent sets of certain regular subgraphs of the derangement graph

The derangement graph is the Cayley graph on the symmetric group \(\mathcal {S}_{n}\) whose generating set \(D_{n}\) is the set of permutations on \([n]=\{1, \ldots , n\}\) without any 1-cycle. For any fixed positive integer \(k \le n\), the Cayley graph generated by the subset of \(D_{n}\) consisting of permutations without any i-cycles for all \(1 \le i \le k\) is a regular subgraph of the derangement graph. In this paper, we determine the smallest eigenvalue of these subgraphs and show that the set of all the largest independent sets in these subgraphs is equal to the set of all the largest independent sets in the derangement graph, provided n is sufficiently large in terms of k.     

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\).     

Conformally Covariant Differential Operators for the Diagonal Action of $$O(p,\,q)$$ on Real Quadrics

Let \(X=G/P\) be a real projective quadric, where \(G=O(p,\,q)\) and P is a parabolic subgroup of G. Let \((\pi _{\lambda ,\epsilon },\, \mathcal H_{\lambda ,\epsilon })_{ (\lambda ,\epsilon )\in {\mathbb {C}}\times \{\pm \}}\) be the family of (smooth) representations of G induced from the characters of P. For \((\lambda ,\, \epsilon ),\, (\mu ,\, \eta )\in {\mathbb {C}}\times \{\pm \},\) a differential operator \(\mathbf D_{(\mu ,\eta )}^\mathrm{reg}\) on \(X\times X,\) acting G-covariantly from \({\mathcal {H}}_{\lambda ,\epsilon } \otimes {\mathcal {H}}_{\mu , \eta }\) into \({\mathcal {H}}_{\lambda +1,-\epsilon } \otimes {\mathcal {H}}_{\mu +1, -\eta }\) is constructed.     

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.     

Induced Cycles in Graphs

The maximum number vertices of a graph G inducing a 2-regular subgraph of G is denoted by \(c_\mathrm{ind}(G)\). We prove that if G is an r-regular graph of order n, then \(c_\mathrm{ind}(G) \ge \frac{n}{2(r-1)} + \frac{1}{(r-1)(r-2)}\) and we prove that if G is a cubic, claw-free graph on order n, then \(c_\mathrm{ind}(G) > \frac{13}{20}n\) and this bound is asymptotically best possible.     

Relationships Between the 2-Metric Dimension and the 2-Adjacency Dimension in the Lexicographic Product of Graphs

Given a connected simple graph \(G=(V(G),E(G))\), a set \(S\subseteq V(G)\) is said to be a 2-metric generator for G if and only if for any pair of different vertices \(u,v\in V(G)\), there exist at least two vertices \(w_1,w_2\in S\) such that \(d_G(u,w_i)\ne d_G(v,w_i)\), for every \(i\in \{1,2\}\), where \(d_G(x,y)\) is the length of a shortest path between x and y. The minimum cardinality of a 2-metric generator is the 2-metric dimension of G, denoted by \(\dim _2(G)\). The metric \(d_{G,2}: V(G)\times V(G)\longmapsto {\mathbb {N}}\cup \{0\}\) is defined as \(d_{G,2}(x,y)=\min \{d_G(x,y),2\}\). Now, a set \(S\subseteq V(G)\) is a 2-adjacency generator for G, if for every two vertices \(x,y\in V(G)\) there exist at least two vertices \(w_1,w_2\in S\), such that \(d_{G,2}(x,w_i)\ne d_{G,2}(y,w_i)\) for every \(i\in \{1,2\}\). The minimum cardinality of a 2-adjacency generator is the 2-adjacency dimension of G, denoted by \({\mathrm {adim}}_2(G)\). In this article, we obtain closed formulae for the 2-metric dimension of the lexicographic product \(G\circ H\) of two graphs G and H. Specifically, we show that \(\dim _2(G\circ H)=n\cdot {\mathrm {adim}}_2(H)+f(G,H),\) where \(f(G,H)\ge 0\), and determine all the possible values of f(G, H).     

Conflict free colorings of (strongly) almost disjoint set-systems

\(f\: \cup {\mathcal {A}}\to {\rho}\) is called a conflict free coloring of the set-system\({\mathcal {A}}\)(withρcolors) if

$\forall A\in {\mathcal {A}}\ \exists\, {\zeta}<{\rho} (|A\cap f^{-1}\{{\zeta}\}|=1).$

The conflict free chromatic number\(\operatorname {\chi _{\rm CF}}\, ({\mathcal {A}})\) of \({\mathcal {A}}\) is the smallest ρ for which \({\mathcal {A}}\) admits a conflict free coloring with ρ colors.

\({\mathcal {A}}\) is a (λ,κ,μ)-system if \(|{\mathcal {A}}| = \lambda\), |A|=κ for all \(A \in {\mathcal {A}}\), and \({\mathcal {A}}\) is μ-almost disjoint, i.e. |A∩A′|<μ for distinct \(A, A'\in {\mathcal {A}}\). Our aim here is to study

$\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,\mu) = \sup \{\operatorname {\chi _{\rm CF}}\, ({\mathcal {A}})\: {\mathcal {A}}\mbox{ is a } (\lambda,\kappa,\mu)\mbox{-system}\}$

for λ≧κ≧μ, actually restricting ourselves to λ≧ω and μ≦ω.

For instance, we prove that

? for any limit cardinal κ (or κ=ω) and integers n≧0, k>0, GCH implies

$\operatorname {\chi _{\rm CF}}\, (\kappa^{+n},t,k+1) =\begin{cases}\kappa^{+(n+1-i)}&; \text{if \ } i\cdot k < t \le (i+1)\cdot k,\ i =1,\dots,n;\\[2pt]\kappa&; \text{if \ } (n+1)\cdot k < t;\end{cases}$

? if λ≧κ≧ω>d>1, then λ<κ ^+ω implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,d) <\omega\) and λ≧? _ω (κ) implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,d) = \omega\);? GCH implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,\omega) \le \omega_{2}\) for λ≧κ≧ω ₂ and V=L implies \(\operatorname {\chi _{\rm CF}}\, (\lambda,\kappa,\omega) \le \omega_{1}\) for λ≧κ≧ω ₁;? the existence of a supercompact cardinal implies the consistency of GCH plus \(\operatorname {\chi _{\rm CF}}\,(\aleph_{\omega+1},\omega_{1},\omega)= \aleph_{\omega+1}\) and \(\operatorname {\chi _{\rm CF}}\, (\aleph_{\omega+1},\omega_{n},\omega) = \omega_{2}\) for 2≦n≦ω;? CH implies \(\operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega,\omega) = \operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega_{1},\omega) = \omega_{1}\), while \(MA_{\omega_{1}}\) implies \(\operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega,\omega) = \operatorname {\chi _{\rm CF}}\, (\omega_{1},\omega_{1},\omega) = \omega\).     

On the least distance eigenvalues of the second power of a graph

The k-th power of a graph G, denoted by \(G^k\), is the graph obtained from G by adding an edge between each pair of vertices with distance at most k. This paper investigates the least distance eigenvalues of the second power of a connected graph, and determine the trees and unicyclic graphs with least distance eigenvalues of the second power in \([-\,3,-\,2]\) and \((-\,\frac{3+\sqrt{5}}{2}, -\,1]\), respectively.     

A generalization of total graphs

Let R be a commutative ring with nonzero identity, \(L_{n}(R)\) be the set of all lower triangular \(n\times n\) matrices, and U be a triangular subset of \(R^{n}\), i.e., the product of any lower triangular matrix with the transpose of any element of U belongs to U. The graph \(GT^{n}_{U}(R^n)\) is a simple graph whose vertices consists of all elements of \(R^{n}\), and two distinct vertices \((x_{1},\dots ,x_{n})\) and \((y_{1},\dots ,y_{n})\) are adjacent if and only if \((x_{1}+y_{1}, \ldots ,x_{n}+y_{n})\in U\). The graph \(GT^{n}_{U}(R^n)\) is a generalization for total graphs. In this paper, we investigate the basic properties of \(GT^{n}_{U}(R^n)\). Moreover, we study the planarity of the graphs \(GT^{n}_{U}(U)\), \(GT^{n}_{U}(R^{n}{\setminus } U)\) and \(GT^{n}_{U}(R^n)\).     

Induced-Universal Graphs for Graphs with Bounded Maximum Degree

For a family \(\mathcal {F}\) of graphs, a graph U is induced-universal for \({\mathcal{F}}\) if every graph in \({\mathcal{F}}\) is an induced subgraph of U. We give a construction for an induced-universal graph for the family of graphs on n vertices with degree at most r, which has \(Cn^{\lfloor (r+1)/2\rfloor}\) vertices and \(Dn^{2\lfloor (r+1)/2\rfloor -1}\) edges, where C and D are constants depending only on r. This construction is nearly optimal when r is even in that such an induced-universal graph must have at least cn ^r/2 vertices for some c depending only on r.Our construction is explicit in that no probabilistic tools are needed to show that the graph exists or that a given graph is induced-universal. The construction also extends to multigraphs and directed graphs with bounded degree.     

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\).     

Perfect state transfer in Laplacian quantum walk

For a graph G and a related symmetric matrix M, the continuous-time quantum walk on G relative to M is defined as the unitary matrix \(U(t) = \exp (-itM)\), where t varies over the reals. Perfect state transfer occurs between vertices u and v at time \(\tau \) if the (u, v)-entry of \(U(\tau )\) has unit magnitude. This paper studies quantum walks relative to graph Laplacians. Some main observations include the following closure properties for perfect state transfer. If an n-vertex graph has perfect state transfer at time \(\tau \) relative to the Laplacian, then so does its complement if \(n\tau \in 2\pi {\mathbb {Z}}\). As a corollary, the join of \(\overline{K}_{2}\) with any m-vertex graph has perfect state transfer relative to the Laplacian if and only if \(m \equiv 2\pmod {4}\). This was previously known for the join of \(\overline{K}_{2}\) with a clique (Bose et al. in Int J Quant Inf 7:713–723, 2009). If a graph G has perfect state transfer at time \(\tau \) relative to the normalized Laplacian, then so does the weak product \(G \times H\) if for any normalized Laplacian eigenvalues \(\lambda \) of G and \(\mu \) of H, we have \(\mu (\lambda -1)\tau \in 2\pi {\mathbb {Z}}\). As a corollary, a weak product of \(P_{3}\) with an even clique or an odd cube has perfect state transfer relative to the normalized Laplacian. It was known earlier that a weak product of a circulant with odd integer eigenvalues and an even cube or a Cartesian power of \(P_{3}\) has perfect state transfer relative to the adjacency matrix. As for negative results, no path with four vertices or more has antipodal perfect state transfer relative to the normalized Laplacian. This almost matches the state of affairs under the adjacency matrix (Godsil in Discret Math 312(1):129–147, 2011).     

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.     

Spectral multiplier theorems and averaged <Emphasis Type="Italic">R</Emphasis>-boundedness

Let A be a 0-sectorial operator with a bounded \(H^\infty (\Sigma _\sigma )\)-calculus for some \(\sigma \in (0,\pi ),\) e.g. a Laplace type operator on \(L^p(\Omega ),\, 1< p < \infty ,\) where \(\Omega \) is a manifold or a graph. We show that A has a \(\mathcal {H}^\alpha _2(\mathbb {R}_+)\) Hörmander functional calculus if and only if certain operator families derived from the resolvent \((\lambda - A)^{-1},\) the semigroup \(e^{-zA},\) the wave operators \(e^{itA}\) or the imaginary powers \(A^{it}\) of A are R-bounded in an \(L^2\)-averaged sense. If X is an \(L^p(\Omega )\) space with \(1 \le p < \infty \), R-boundedness reduces to well-known estimates of square sums.     

Monochromatic Solutions for Multi-Term Unknowns

Given integers \(k\ge 2\), \(n \ge 2\), \(m \ge 2\) and \( a_1,a_2,\ldots ,a_m \in {\mathbb {Z}}{\backslash }{\{0\}}\), and let \(f(z)= \sum _{j=0}^{n}c_jz^j\) be a polynomial of integer coefficients with \(c_n>0\) and \((\sum _{i=1}^ma_i)|f(z)\) for some integer z. For a k-coloring of \([N]=\{1,2,\ldots ,N\}\), we say that there is a monochromatic solution of the equation \(a_1x_1+a_2x_2+\cdots +a_mx_m=f(z)\) if there exist pairwise distinct \(x_1,x_2,\ldots ,x_m\in [N]\) all of the same color such that the equation holds for some \(z\in \mathbb {Z}\). Problems of this type are often referred to as Ramsey-type problems. In this paper, it is shown that if \(a_i>0\) for \(1\le i\le m\), then there exists an integer \(N_0=N(k,m,n)\) such that for \(N\ge N_0\), each k-coloring of [N] contains a monochromatic solution \(x_1,x_2,\ldots ,x_m\) of the equation \(a_1x_1+a_2x_2+ \cdots +a_mx_m= f(z)\). Moreover, if n is odd and there are \(a_i\) and \(a_j\) such that \(a_ia_j<0\) for some \(1 \le i\ne j\le m\), then the assertion holds similarly.     

On Filtered Polynomial Approximation on the Sphere

This paper considers filtered polynomial approximations on the unit sphere \(\mathbb {S}^d\subset \mathbb {R}^{d+1}\), obtained by truncating smoothly the Fourier series of an integrable function f with the help of a “filter” h, which is a real-valued continuous function on \([0,\infty )\) such that \(h(t)=1\) for \(t\in [0,1]\) and \(h(t)=0\) for \(t\ge 2\). The resulting “filtered polynomial approximation” (a spherical polynomial of degree \(2L-1\)) is then made fully discrete by approximating the inner product integrals by an N-point cubature rule of suitably high polynomial degree of precision, giving an approximation called “filtered hyperinterpolation”. In this paper we require that the filter h and all its derivatives up to \(\lfloor \tfrac{d-1}{2}\rfloor \) are absolutely continuous, while its right and left derivatives of order \(\lfloor \tfrac{d+1}{2}\rfloor \) exist everywhere and are of bounded variation. Under this assumption we show that for a function f in the Sobolev space \(W^s_p(\mathbb {S}^d),\ 1\le p\le \infty \), both approximations are of the optimal order \( L^{-s}\), in the first case for \(s>0\) and in the second fully discrete case for \(s>d/p\), conditions which in both cases cannot be weakened.     

Regularity of powers of bipartite graphs

Let G be a finite simple graph and I(G) denote the corresponding edge ideal. For all \(s \ge 1\), we obtain upper bounds for \({\text {reg}}(I(G)^s)\) for bipartite graphs. We then compare the properties of G and \(G'\), where \(G'\) is the graph associated with the polarization of the ideal \((I(G)^{s+1} : e_1\cdots e_s)\), where \(e_1,\cdots , e_s\) are edges of G. Using these results, we explicitly compute \({\text {reg}}(I(G)^s)\) for several subclasses of bipartite graphs.     

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\).