A Tight Upper Bound on Acquaintance Time of Graphs

In this note we confirm a conjecture raised by Benjamini et al. (SIAM J Discrete Math 28(2):767–785, 2014) on the acquaintance time of graphs, proving that for all graphs G with n vertices it holds that \(\mathcal {AC}(G) = O(n^{3/2})\). This is done by proving that for all graphs G with n vertices and maximum degree \(\varDelta \) it holds that \(\mathcal {AC}(G) \le 20 \varDelta n\). Combining this with the bound \(\mathcal {AC}(G) \le O(n^2/\varDelta )\) from Benjamini et al. (SIAM J Discrete Math 28(2):767–785, 2014) gives the uniform upper bound of \(O(n^{3/2})\) for all n-vertex graphs. This bound is tight up to a multiplicative constant. We also prove that for the n-vertex path \(P_n\) it holds that \(\mathcal {AC}(P_n)=n-2\). In addition we show that the barbell graph \(B_n\) consisting of two cliques of sizes \({\lceil n/2\rceil }\) and \({\lfloor n/2\rfloor }\) connected by a single edge also has \(\mathcal {AC}(B_n) = n-2\). This shows that it is possible to add \(\varOmega (n^2\)) edges a graph without changing its \(\mathcal {AC}\) value.     

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.     

On Modular Edge-Graceful Graphs

Let G be a connected graph of order \({n\ge 3}\) and size m and \({f:E(G)\to \mathbb{Z}_n}\) an edge labeling of G. Define a vertex labeling \({f': V(G)\to \mathbb{Z}_n}\) by \({f'(v)= \sum_{u\in N(v)}f(uv)}\) where the sum is computed in \({\mathbb{Z}_n}\) . If f′ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A graph G is modular edge-graceful if G contains a modular edge-graceful spanning tree. Several classes of modular edge-graceful trees are determined. For a tree T of order n where \({n\not\equiv 2 \pmod 4}\) , it is shown that if T contains at most two even vertices or the set of even vertices of T induces a path, then T is modular edge-graceful. It is also shown that every tree of order n where \({n\not\equiv 2\pmod 4}\) having diameter at most 5 is modular edge-graceful.     

On complete sequences

A sequence A of nonnegative integers is called complete if all sufficiently large integers can be represented as the sum of distinct terms taken form A. For a sequence \({S=\{s_{1}, s_{2}, \dots\}}\) of positive integers and a positive real number α, let S _α denote the sequence \({\{\lfloor\alpha s_{1}\rfloor, \lfloor\alpha s_{2}\rfloor, \dots\}}\), where \({\lfloor x \rfloor}\) denotes the greatest integer not greater than x. Let \({{U_S = \{\alpha \mid S_\alpha} \, is complete\}}\). Hegyvári [6] proved that if \({\lim_{n\to\infty} (s_{n+1}-s_{n})=+ \infty}\), \({s_{n+1} < \gamma s_{n}}\) for all integers \({n \geqq n_{0}}\), where \({1 < \gamma < 2}\), and \({U_{S}\ne\emptyset}\), then \({\mu(U_{S}) > 0}\), where \({\mu(U_{S})}\) is the Lebesgue measure of U _S . Yong-Gao Chen and the first author [4] proved that, if \({s_{n+1} < \gamma s_{n}}\) for all integers \({n \geqq n_{0}}\), where \({1 < \gamma \leqq 7/4=1.75}\), then \({\mu(U_{S}) > 0}\). In this paper, we prove that the conclusion holds for \({1 < \gamma \leqq \sqrt[4]{13}=1.898\dots\;}\).     

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.     

Conflict free colorings of nonuniform systems of infinite sets

If \(\mathcal{H}\) is a system of infinite sets, |A∩B|<r for \({A\ne B\in\mathcal{H}}\) (r<ω) then \(\mathcal{H}\) has a conflict free coloring with ω colors, i.e., a function \(F\colon {\bigcup\mathcal{H}\to\omega}\) so that each \(A\in\mathcal{H}\) has a color i<ω with |F ^?1(i)∩A|=1.     

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.     

Facets of the <Emphasis Type="Italic">r</Emphasis>-Stable (<Emphasis Type="Italic">n</Emphasis>, <Emphasis Type="Italic">k</Emphasis>)-Hypersimplex

Let k, n, and r be positive integers with k < n and \({r \leq \lfloor \frac{n}{k} \rfloor}\). We determine the facets of the r-stable n, k-hypersimplex. As a result, it turns out that the r-stable n, k-hypersimplex has exactly 2n facets for every \({r < \lfloor \frac{n}{k} \rfloor}\). We then utilize the equations of the facets to study when the r-stable hypersimplex is Gorenstein. For every k > 0 we identify an infinite collection of Gorenstein r-stable hypersimplices, consequently expanding the collection of r-stable hypersimplices known to have unimodal Ehrhart \({\delta}\)-vectors.     

Resilience of ranks of higher inclusion matrices

Let \(n \ge r \ge s \ge 0\) be integers and \(\mathcal {F}\) a family of r-subsets of [n]. Let \(W_{r,s}^{\mathcal {F}}\) be the higher inclusion matrix of the subsets in \({{\mathcal {F}}}\) vs. the s-subsets of [n]. When \(\mathcal {F}\) consists of all r-subsets of [n], we shall simply write \(W_{r,s}\) in place of \(W_{r,s}^{\mathcal {F}}\). In this paper we prove that the rank of the higher inclusion matrix \(W_{r,s}\) over an arbitrary field K is resilient. That is, if the size of \(\mathcal {F}\) is “close” to \({n \atopwithdelims ()r}\) then \({{\mathrm{rank}}}_{K}( W_{r,s}^{\mathcal {F}}) = {{\mathrm{rank}}}_{K}(W_{r,s})\), where K is an arbitrary field. Furthermore, we prove that the rank (over a field K) of the higher inclusion matrix of r-subspaces vs. s-subspaces of an n-dimensional vector space over \({\mathbb {F}}_q\) is also resilient if \(\mathrm{char}(K)\) is coprime to q.     

Hankel Determinants of Random Moment Sequences

For \(t \in [0,1]\) let \(\underline{H}_{2\lfloor nt \rfloor } = (m_{i+j})_{i,j=0}^{\lfloor nt \rfloor }\) denote the Hankel matrix of order \(2\lfloor nt \rfloor \) of a random vector \((m_1,\ldots ,m_{2n})\) on the moment space \(\mathcal {M}_{2n}(I)\) of all moments (up to the order 2n) of probability measures on the interval \(I \subset \mathbb {R}\). In this paper we study the asymptotic properties of the stochastic process \(\{ \log \det \underline{H}_{2\lfloor nt \rfloor } \}_{t\in [0,1]}\) as \(n \rightarrow \infty \). In particular weak convergence and corresponding large deviation principles are derived after appropriate standardization.     

Inflation of Finite Lattices Along All-or-nothing Sets

We introduce a new generalization of Alan Day’s doubling construction. For ordered sets \(\mathcal {L}\) and \(\mathcal {K}\) and a subset \(E \subseteq \ \leq _{\mathcal {L}}\) we define the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) arising from inflation of \(\mathcal {L}\) along E by \(\mathcal {K}\). Under the restriction that \(\mathcal {L}\) and \(\mathcal {K}\) are finite lattices, we find those subsets \(E \subseteq \ \leq _{\mathcal {L}}\) such that the ordered set \(\mathcal {L} \star _{E} \mathcal {K}\) is a lattice. Finite lattices that can be constructed in this way are classified in terms of their congruence lattices.A finite lattice is binary cut-through codable if and only if there exists a 0?1 spanning chain \(\left \{\theta _{i}\colon 0 \leq i \leq n \right \}\) in \(Con(\mathcal {L})\) such that the cardinality of the largest block of ?? _i /?? _i?1 is 2 for every i with 1≤i≤n. These are exactly the lattices that can be constructed by inflation from the 1-element lattice using only the 2-element lattice. We investigate the structure of binary cut-through codable lattices and describe an infinite class of lattices that generate binary cut-through codable varieties.     

The power graph on the conjugacy classes of a finite group

A digraph \({\overrightarrow{\mathcal{Pc}}(G)}\) is said to be the directed power graph on the conjugacy classes of a group G, if its vertices are the non-trivial conjugacy classes of G, and there is an arc from vertex C to C′ if and only if \({C \neq C'}\) and \({C \subseteqq {C'}^{m}}\) for some positive integer \({m > 0}\). Moreover, the simple graph \({\mathcal{Pc}(G)}\) is said to be the (undirected) power graph on the conjugacy classes of a group G if its vertices are the conjugacy classes of G and two distinct vertices C and C′ are adjacent in \({\mathcal{Pc}(G)}\) if one is a subset of a power of the other. In this paper, we find some connections between algebraic properties of some groups and properties of the associated graph.     

Partial permutation decoding for binary linear and $$Z_4$$-linear Hadamard codes

In this paper, s-\({\text {PD}}\)-sets of minimum size \(s+1\) for partial permutation decoding for the binary linear Hadamard code \(H_m\) of length \(2^m\), for all \(m\ge 4\) and \(2 \le s \le \lfloor {\frac{2^m}{1+m}}\rfloor -1\), are constructed. Moreover, recursive constructions to obtain s-\({\text {PD}}\)-sets of size \(l\ge s+1\) for \(H_{m+1}\) of length \(2^{m+1}\), from an s-\({\text {PD}}\)-set of the same size for \(H_m\), are also described. These results are generalized to find s-\({\text {PD}}\)-sets for the \({\mathbb {Z}}_4\)-linear Hadamard codes \(H_{\gamma , \delta }\) of length \(2^m\), \(m=\gamma +2\delta -1\), which are binary Hadamard codes (not necessarily linear) obtained as the Gray map image of quaternary linear codes of type \(2^\gamma 4^\delta \). Specifically, s-PD-sets of minimum size \(s+1\) for \(H_{\gamma , \delta }\), for all \(\delta \ge 3\) and \(2\le s \le \lfloor {\frac{2^{2\delta -2}}{\delta }}\rfloor -1\), are constructed and recursive constructions are described.     

Distance-regular graphs of large diameter that are completely regular clique graphs

A connected graph is said to be a completely regular clique graph with parameters (s, c), \(s, c \in {\mathbb {N}}\), if there is a collection \(\mathcal {C}\) of completely regular cliques of size \(s+1\) such that every edge is contained in exactly c members of \(\mathcal {C}\). It is known that many families of distance-regular graphs are completely regular clique graphs. In this paper, we determine completely regular clique graph structures, i.e., the choices of \(\mathcal {C}\), of all known families of distance-regular graphs with unbounded diameter. In particular, we show that all distance-regular graphs in this category are completely regular clique graphs except the Doob graphs, the twisted Grassmann graphs and the Hermitean forms graphs. We also determine parameters (s, c); however, in a few cases we determine only s and give a bound on the value c. Our result is a generalization of a series of works by J. Hemmeter and others who determined distance-regular graphs in this category that are bipartite halves of bipartite distance-regular graphs.     

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

Malcev products of unipotent monoids and varieties of bands

Let \(\mathcal{U}\) be the class of all unipotent monoids and \(\mathcal{B}\) the variety of all bands. We characterize the Malcev product \(\mathcal{U} \circ \mathcal{V}\) where \(\mathcal{V}\) is a subvariety of \(\mathcal{B}\) low in its lattice of subvarieties, \(\mathcal{B}\) itself and the subquasivariety \(\mathcal{S} \circ \mathcal{RB}\), where \(\mathcal{S}\) stands for semilattices and \(\mathcal{RB}\) for rectangular bands, in several ways including by a set of axioms. For members of some of them we describe the structure as well. This succeeds by using the relation \(\widetilde{\mathcal{H}}= \widetilde{\mathcal{L}} \cap \widetilde{\mathcal{R}}\), where \(a\;\,\widetilde{\mathcal{L}}\;\,b\) if and only if a and b have the same idempotent right identities, and \(\widetilde{\mathcal{R}}\) is its dual.We also consider \((\mathcal{U} \circ \mathcal{RB}) \circ \mathcal{S}\) which provides the motivation for this study since \((\mathcal{G} \circ \mathcal{RB}) \circ \mathcal{S}\) coincides with completely regular semigroups, where \(\mathcal{G}\) is the variety of all groups. All this amounts to a generalization of the latter: \(\mathcal{U}\) instead of \(\mathcal{G}\).     

The Leavitt Path Algebras of Generalized Cayley Graphs

Let n be a positive integer. For each \({0 \leq j \leq n-1}\), we let \({C_{n}^{j}}\) denote Cayley graph for the cyclic group \({\mathbb{Z}_n}\) with respect to the subset \({\{1, j\}}\). For any such pair (n, j), we compute the size of the Grothendieck group of the Leavitt path algebra \({L_K(C_{n}^{j})}\); the analysis is related to a collection of integer sequences described by Haselgrove in the 1940s. When j = 0, 1, or 2, we are able to extract enough additional information about the structure of these Grothendieck groups so that we may apply a Kirchberg-Phillips-type result to explicitly realize the algebras \({L_K(C_{n}^{j})}\) as the Leavitt path algebras of graphs having at most three vertices. The analysis in the j = 2 case leads us to some perhaps surprising and apparently nontrivial connections to the classical Fibonacci sequence.     

Walk-Powers and Homomorphism Bounds of Planar Signed Graphs

As an extension of the Four-Color Theorem it is conjectured by the first author that every planar graph of odd-girth at least \(2k+1\) admits a homomorphism to the projective cube of dimension 2k, i.e., the Cayley graph \({\mathcal {PC}}(2k)=({\mathbb {Z}}_2^{2k}, \{e_1, e_2,\) \(\ldots ,e_{2k}, J\})\) where the \(e_i\)’s are the standard basis vectors of \({\mathbb {Z}}_2^d\) and J is the all 1 vector. Noting that \({\mathcal {PC}}(2k)\) itself is of odd-girth \(2k+1\), in this work we show that if the conjecture is true, then \({\mathcal {PC}}(2k)\) is an optimal such graph both with respect to the number of vertices and the number of edges. The result is obtained using the notion of walk-power of graphs and their clique numbers. An analogous result is proved for signed bipartite planar graphs of unbalanced-girth 2k. The work is presented in the uniform framework of planar consistent signed graphs.     

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.     

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