On a problem of Erdős and Moser

A set A of vertices in an r-uniform hypergraph \(\mathcal H\) is covered in \(\mathcal H\) if there is some vertex \(u\not \in A\) such that every edge of the form \(\{u\}\cup B\), \(B\in A^{(r-1)}\) is in \(\mathcal H\). Erd?s and Moser (J Aust Math Soc 11:42–47, 1970) determined the minimum number of edges in a graph on n vertices such that every k-set is covered. We extend this result to r-uniform hypergraphs on sufficiently many vertices, and determine the extremal hypergraphs. We also address the problem for directed graphs.     

Connection between the clique number and the Lagrangian of 3-uniform hypergraphs

There is a remarkable connection between the clique number and the Lagrangian of a 2-graph proved by Motzkin and Straus (J Math 17:533–540, 1965). It would be useful in practice if similar results hold for hypergraphs. However, the obvious generalization of Motzkin and Straus’ result to hypergraphs is false. Frankl and Füredi conjectured that the r-uniform hypergraph with m edges formed by taking the first m sets in the colex ordering of \({\mathbb N}^{(r)}\) has the largest Lagrangian of all r-uniform hypergraphs with m edges. For \(r=2\), Motzkin and Straus’ theorem confirms this conjecture. For \(r=3\), it is shown by Talbot that this conjecture is true when m is in certain ranges. In this paper, we explore the connection between the clique number and Lagrangians for 3-uniform hypergraphs. As an application of this connection, we confirm that Frankl and Füredi’s conjecture holds for bigger ranges of m when \(r=3\). We also obtain two weaker versions of Turán type theorem for left-compressed 3-uniform hypergraphs.     

Every 3-connected $$\{K_{1,3},N_{1,2,3}\}$$-free graph is Hamilton-connected

A graph G is \(\{X,Y\}\)-free if it contains neither X nor Y as an induced subgraph. Pairs of connected graphs X, Y such that every 3-connected \(\{X,Y\}\)-free graph is Hamilton-connected have been investigated recently in (2002, 2000, 2012). In this paper, it is shown that every 3-connected \(\{K_{1,3},N_{1,2,3}\}\)-free graph is Hamilton-connected, where \(N_{1,2,3}\) is the graph obtained by identifying end vertices of three disjoint paths of lengths 1, 2, 3 to the vertices of a triangle.     

A Twelve Vertex Theorem for 3-Connected Claw-Free Graphs

The cyclability of a graph H, denoted by C(H), is the largest integer r such that H has a cycle through any r vertices. For a claw-free graph H, by Ryjá?ek (J Comb Theory Ser B 70:217–224, 1997) closure concept, there is a \(K_3\)-free graph G such that the closure \(cl(H)=L(G)\). In this note, we prove that for a 3-connected claw-free graph H with its closure \(cl(H)=L(G)\), \(C(H)\ge 12\) if and only if G can not be contracted to the Petersen graph in such a way that each vertex in P is obtained by contracting a nontrivial connected \(K_3\)-free subgraph. This is an improvement of the main result in Györi and Plummer (Stud Sci Math Hung 38:233–244, 2001).     

Comparison of graphs associated to a commutative Artinian ring

Let R be a commutative ring with \(1\ne 0\) and the additive group \(R^+\). Several graphs on R have been introduced by many authors, among zero-divisor graph \(\Gamma _1(R)\), co-maximal graph \(\Gamma _2(R)\), annihilator graph AG(R), total graph \( T(\Gamma (R))\), cozero-divisors graph \(\Gamma _\mathrm{c}(R)\), equivalence classes graph \(\Gamma _\mathrm{E}(R)\) and the Cayley graph \(\mathrm{Cay}(R^+ ,Z^*(R))\). Shekarriz et al. (J. Commun. Algebra, 40 (2012) 2798–2807) gave some conditions under which total graph is isomorphic to \(\mathrm{Cay}(R^+ ,Z^*(R))\). Badawi (J. Commun. Algebra, 42 (2014) 108–121) showed that when R is a reduced ring, the annihilator graph is identical to the zero-divisor graph if and only if R has exactly two minimal prime ideals. The purpose of this paper is comparison of graphs associated to a commutative Artinian ring. Among the results, we prove that for a commutative finite ring R with \(|\mathrm{Max}(R)|=n \ge 3\), \( \Gamma _1(R) \simeq \Gamma _2(R)\) if and only if \(R\simeq \mathbb {Z}^n_2\); if and only if \(\Gamma _1(R) \simeq \Gamma _\mathrm{E}(R)\). Also the annihilator graph is identical to the cozero-divisor graph if and only if R is a Frobenius ring.     

Homotopy type of neighborhood complexes of Kneser graphs, $$\varvec{KG_{2,k}}$$

Schrijver (Nieuw Archief voor Wiskunde, 26(3) (1978) 454–461) identified a family of vertex critical subgraphs of the Kneser graphs called the stable Kneser graphs \(SG_{n,k}\). Björner and de Longueville (Combinatorica 23(1) (2003) 23–34) proved that the neighborhood complex of the stable Kneser graph \(SG_{n,k}\) is homotopy equivalent to a k-sphere. In this article, we prove that the homotopy type of the neighborhood complex of the Kneser graph \(KG_{2,k}\) is a wedge of \((k+4)(k+1)+1\) spheres of dimension k. We construct a maximal subgraph \(S_{2,k}\) of \(KG_{2,k}\), whose neighborhood complex is homotopy equivalent to the neighborhood complex of \(SG_{2,k}\). Further, we prove that the neighborhood complex of \(S_{2,k}\) deformation retracts onto the neighborhood complex of \(SG_{2,k}\).     

Chvátal–Erdös Type Conditions for Hamiltonicity of Claw-Free Graphs

For a graph H, let \(\alpha (H)\) and \(\alpha ^{\prime }(H)\) denote the independence number and the matching number, respectively. Let \(k\ge 2\) and \(r>0\) be given integers. We prove that if H is a k-connected claw-free graph with \(\alpha (H)\le r\), then either H is Hamiltonian or the Ryjá c? ek’s closure \(cl(H)=L(G)\) where G can be contracted to a k-edge-connected \(K_3\)-free graph \(G_0^{\prime }\) with \(\alpha ^{\prime }(G_0^{\prime })\le r\) and \(|V(G_0^{\prime })|\le \max \{3r-5, 2r+1\}\) if \(k\ge 3\) or \(|V(G_0^{\prime })|\le \max \{4r-5, 2r+1\}\) if \(k=2\) and \(G_0^{\prime }\) does not have a dominating closed trail containing all the vertices that are obtained by contracting nontrivial subgraphs. As corollaries, we prove the following:

1. (a)
   A 2-connected claw-free graph H with \(\alpha (H)\le 3\) is either Hamiltonian or \(cl(H)=L(G)\) where G is obtained from \(K_{2,3}\) by adding at least one pendant edge on each degree 2 vertex;
    
2. (b)
   A 3-connected claw-free graph H with \(\alpha (H)\le 7\) is either Hamiltonian or \(cl(H)=L(G)\) where G is a graph with \(\alpha ^{\prime }(G)=7\) that is obtained from the Petersen graph P by adding some pendant edges or subdividing some edges of P.
    

Case (a) was first proved by Xu et al. [19]. Case (b) is an improvement of a result proved by Flandrin and Li [12]. For a given integer \(r>0\), the number of graphs of order at most \(\max \{4r-5, 2r+1\}\) is fixed. The main result implies that improvements to case (a) or (b) by increasing the value of r and by enlarging the collection of exceptional graphs can be obtained with the help of a computer. Similar results involved degree or neighborhood conditions are also discussed.

     

Solution to a Problem on Hamiltonicity of Graphs Under Ore- and Fan-Type Heavy Subgraph Conditions

A graph G is called claw-o-heavy if every induced claw (\(K_{1,3}\)) of G has two end-vertices with degree sum at least |V(G)|. For a given graph S,  G is called S-f-heavy if for every induced subgraph H of G isomorphic to S and every pair of vertices \(u,v\in V(H)\) with \(d_H(u,v)=2,\) there holds \(\max \{d(u),d(v)\}\ge |V(G)|/2.\) In this paper, we prove that every 2-connected claw-o-heavy and \(Z_3\)-f-heavy graph is hamiltonian (with two exceptional graphs), where \(Z_3\) is the graph obtained by identifying one end-vertex of \(P_4\) (a path with 4 vertices) with one vertex of a triangle. This result gives a positive answer to a problem proposed Ning and Zhang (Discrete Math 313:1715–1725, 2013), and also implies two previous theorems of Faudree et al. and Chen et al., respectively.     

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

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

A normal generating set for the Torelli group of a compact non-orientable surface

For a compact surface S, let \({\mathcal {I}}(S)\) denote the Torelli group of S. For a compact orientable surface \(\Sigma \), \({\mathcal {I}}(\Sigma )\) is generated by two types of mapping classes, called bounding simple closed curve maps (BSCC maps) and bounding pair maps (BP maps) (see Powell in Proc Am Math Soc 68:347–350, 1978; Putman in Geom Topol 11:829–865, 2007). For a non-orientable closed surface N, \({\mathcal {I}}(N)\) is generated by BSCC maps and BP maps (see Hirose and Kobayashi in Fund Math 238:29–51, 2017). In this paper, we give an explicit normal generating set for \({\mathcal {I}}(N_g^b)\), where \(N_g^b\) is a genus-g compact non-orientable surface with b boundary components for \(g\ge 4\) and \(b\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.     

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.     

Inverse ambiguous functions on some finite non-abelian groups

In Schmitz (Aequ Math 91:373–389, 2017), the first author defines an “inverse ambiguous function” on a group G to be a bijective function \(f:G \rightarrow G\) satisfying the functional equation \(f^{-1}(x) = (f(x))^{-1}\) for all \(x \in G\). Using a simple criterion involving the number of elements in G not equal to their own inverse, the classification of finite abelian groups admitting inverse ambiguous functions is achieved. In this paper we aim to extend the results from (2017) to determine the existence of inverse ambiguous functions on members of certain families of non-abelian groups, namely the symmetric groups \(S_n\), the alternating groups \(A_n\), and the general linear groups GL(2, q) over a finite field \(\mathbb {F}_q\).     

Hamiltonian Type Properties in Claw-Free $$P_5$$-Free Graphs

A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each integer r in the set \(\{ m, m + 1, \ldots , n \}\). This property, which generalizes the notion of a vertex pancyclic graph, was defined by Faudree et al. in (Graphs Combin 20:291–310, 2004). The notion of (k, m)-pancyclicity provides one way to measure the prevalence of cycles in a graph. Broersma and Veldman showed in (Contemporary methods in graph theory, BI-Wiss.-Verlag, Mannheim, Wien, Zürich, pp 181–194, 1990) that any 2-connected claw-free \(P_5\)-free graph must be hamiltonian. In fact, every non-hamiltonian cycle in such a graph is either extendable or very dense. We show that any 2-connected claw-free \(P_5\)-free graph is (k, 3k)-pancyclic for each integer \(k \ge 2\). We also show that such a graph is (1, 5)-pancyclic. Examples are provided which show that these results are best possible. Each example we provide represents an infinite family of graphs.     

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.     

A generalization of the normal rational curve in $$\mathop {\mathrm{PG}}(d,q^n)$$ and its associated non-linear MRD codes

Let A and B be two points of \(\mathop {\mathrm{PG}}(d,q^n)\) and let \(\Phi \) be a collineation between the stars of lines with vertices A and B, that does not map the line AB into itself. In this paper we prove that if \(d=2\) or \(d\ge 3\) and the lines \(\Phi ^{-1}(AB), AB, \Phi (AB) \) are not in a common plane, then the set \(\mathcal{C}\) of points of intersection of corresponding lines under \(\Phi \) is the union of \(q-1\) scattered \({\mathbb {F}}_{q}\)-linear sets of rank n together with \(\{A,B\}\). As an application we will construct, starting from the set \(\mathcal{C}\), infinite families of non-linear \((d+1, n, q;d-1)\)-MRD codes, \(d\le n-1\), generalizing those recently constructed in Cossidente et al. (Des Codes Cryptogr 79:597–609, 2016) and Durante and Siciliano (Electron J Comb, 2017).     

Clique-Coloring Claw-Free Graphs

A clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. A k-clique-coloring of a graph G is an assignment of k colors to the vertices of G such that no clique of G is monochromatic. Bacsó et al. (SIAM J Discrete Math 17:361–376, 2004) noted that the clique-coloring number is unbounded even for the line graphs of complete graphs. In this paper, we prove that a claw-free graph with maximum degree at most 7, except an odd cycle longer than 3, has a 2-clique-coloring by using a decomposition theorem of Chudnovsky and Seymour (J Combin Theory Ser B 98:839–938, 2008) and the limitation of the degree 7 is necessary since the line graph of \(K_{6}\) is a graph with maximum degree 8 but its clique-coloring number is 3 by the Ramsey number \(R(3,3)=6\). In addition, we point out that, if an arbitrary line graph of maximum degree at most d is m-clique-colorable (\(m\ge 3\)), then an arbitrary claw-free graph of maximum degree at most d is also m-clique-colorable.     

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.     

Asymptotic Delsarte cliques in distance-regular graphs

We give a new bound on the parameter \(\lambda \) (number of common neighbors of a pair of adjacent vertices) in a distance-regular graph G, improving and generalizing bounds for strongly regular graphs by Spielman (1996) and Pyber (2014. arXiv:1409.3041). The new bound is one of the ingredients of recent progress on the complexity of testing isomorphism of strongly regular graphs (Babai et al. 2013). The proof is based on a clique geometry found by Metsch (Des Codes Cryptogr 1(2):99–116, 1991) under certain constraints on the parameters. We also give a simplified proof of the following asymptotic consequence of Metsch’s result: If \(k\mu = o(\lambda ^2)\), then each edge of G belongs to a unique maximal clique of size asymptotically equal to \(\lambda \), and all other cliques have size \(o(\lambda )\). Here k denotes the degree and \(\mu \) the number of common neighbors of a pair of vertices at distance 2. We point out that Metsch’s cliques are “asymptotically Delsarte” when \(k\mu = o(\lambda ^2)\), so families of distance-regular graphs with parameters satisfying \(k\mu = o(\lambda ^2)\) are “asymptotically Delsarte-geometric.”