Search

A 2-edge-coloured graph G is supereulerian if G contains a spanning closed trail in which the edges alternate in colours. We show that for general 2-edge-coloured graphs it is NP-complete to decide whether the graph is supereulerian. An eulerian factor of a 2-edge-coloured graph is a collection of vertex-disjoint induced subgraphs which cover all the vertices of G such that each of these subgraphs is supereulerian. We give a polynomial algorithm to test whether a 2-edge-coloured graph has an eulerian factor and to produce one when it exists. A 2-edge-coloured graph is (trail-)colour-connected if it contains a pair of alternating (u, v)-paths ((u, v)-trails) whose union is an alternating closed walk for every pair of distinct vertices u, v. We prove that a 2-edge-coloured complete bipartite graph is supereulerian if and only if it is colour-connected and has an eulerian factor. A 2-edge-coloured graph is M-closed if xz is an edge of G whenever some vertex u is joined to both x and z by edges of the same colour. M-closed 2-edge-coloured graphs, introduced in Contreras-Balbuena et al. (Discret Math Theoret Comput Sci 21:1, 2019), form a rich generalization of 2-edge-coloured complete graphs. We show that if G is obtained from an M-closed 2-edge-coloured graph H by substituting independent sets for the vertices of H, then G is supereulerian if and only if G is trail-colour-connected and has an eulerian factor. Finally we discuss 2-edge-coloured complete multipartite graphs and show that such a graph may not be supereulerian even if it is trail-colour-connected and has an eulerian factor.

For a graph G, $$L(G)^2$$ L ( G ) 2 is the square of the line graph of G – that is, vertices of $$L(G)^2$$ L ( G ) 2 are edges of G and two edges $$e,f\in E(G)$$ e , f ∈ E ( G ) are adjacent in $$L(G)^2$$ L ( G ) 2 if at least one vertex of e is adjacent to a vertex of f and $$e\ne f$$ e ≠ f . The strong chromatic index of G, denoted by $$s'(G)$$ s ′ ( G ) , is the chromatic number of $$L(G)^2$$ L ( G ) 2 . A strong clique in G is a clique in $$L(G)^2$$ L ( G ) 2 . Finding a bound for the maximum size of a strong clique in a graph with given maximum degree is a problem connected to a famous conjecture of Erdős and Nešetřil concerning strong chromatic index of graphs. In this note we prove that a size of a strong clique in a claw-free graph with maximum degree $$\varDelta $$ Δ is at most $$\varDelta ^2 + \frac{1}{2}\varDelta $$ Δ 2 + 1 2 Δ . This result improves the only known result $$1.125\varDelta ^2+\varDelta $$ 1.125 Δ 2 + Δ , which is a bound for the strong chromatic index of claw-free graphs.

We first introduce the class of bipartite absolute retracts with respect to tree obstructions with at most k leaves. Then, using the theory of homomorphism duality, we show that this class of absolute retracts coincides exactly with the bipartite graphs which admit a $$(k+1)$$ -ary near-unanimity polymorphism. This result mirrors the case for reflexive graphs and generalizes a known result for bipartite graphs which admit a 3-ary near-unanimity polymorphism.

Let G be a 3-connected graph. An edge (a triangle) of G is said to be a 3-contractible edge (a 3-contractible triangle) if the contraction of it results in a 3-connected graph. We denote by $$E_{c}(G)$$ and $$\mathcal {T}_{c}(G)$$ the set of 3-contractible edges of G and the set of 3-contractible triangles of G, respectively. We prove that if $$|V(G)|\ge 7$$ , then $$|E_{c}(G)|+ \frac{15}{14}|\mathcal {T}_{c}(G)|\ge \frac{6}{7}|V(G)|.$$ We also determine the extremal graphs.

A nonzero integral flow f is conformally decomposable if $$f=f_1+f_2$$ , where $$f_1,f_2$$ are nonzero integral flows, both are nonnegative or both are nonpositive. Conformally indecomposable flows on ordinary graphs are simply graph circuit flows. However, on signed graphs without outer-edges (compact case), conformally indecomposable flows, classified by Chen and Wang (arXiv:1112.0642, 2013) and by Chen et al. (Discret Math 340:1271–1286, 2017), are signed-graph circuit flows plus an extra class of characteristic flows of so-called Eulerian circle-trees. This paper is to classify indecomposable conformal integral flows on signed graphs with outer-edges (non-compact case). A notable feature is that with outer-edges the treatment is natural and results become stronger but proofs are simpler than that without outer-edges.

The graph Cheeger constant and Cheeger inequalities are generalized to the case of hypergraphs whose edges have the same cardinality. In particular, it is shown that the second largest eigenvalue of the generalized normalized Laplacian is bounded both above and below by the generalized Cheeger constant, and the corresponding eigenfunctions can be used to approximate the Cheeger cut.

Given ann-sided polygonPon the plane withn≥4n≥4, a quadrangulation ofPis a geometric plane graph such that the boundary of the outer face isPand that each finite face is quadrilateral. Clearly,Pis quadrangulatable (i.e., admits a quadrangulation) only ifnis even, but there is a non-quadrangulatable even-sided polygon. Ramaswami et al. [Comp Geom 9:257–276, (1998)] proved that everyn-sided polygonPwithn≥4n≥4even admits a quadrangulation with at most⌊n−24⌋⌊n−24⌋Steiner points, where a Steiner point forPis an auxiliary point which can be put in any position in the interior ofP. In this paper, introducing the notion of the spirality ofPto control a structure ofP(independent ofn), we estimate the number of Steiner points to quadrangulateP., This is a post-peer-review, pre-copyedit version of an article published in Graphs and Combinatorics. The final authenticated version is available online at: https://doi.org/10.1007/s00373-021-02346-1

An edge-colored graph is called rainbow (or heterochromatic) if all its edges have distinct colors. It is known that if an edge-colored connected graph H has minimum color degree at least |H|/2 and has a certain property, then H has a rainbow spanning tree. In this paper, we prove that if an edge-colored connected bipartite graph G has minimum color degree at least |G|/3 and has a certain property, then G has a rainbow spanning tree. We also give a similar sufficient condition for G to have a properly colored spanning tree. Moreover, we show that these minimum color-degree conditions are sharp.

For two graphs $$G_1$$ and $$G_2$$ , the star-critical Ramsey number $$r_*(G_1,G_2)$$ is the minimum integer k such that any red/blue edge-coloring of $$K_{r-1}\sqcup K_{1,k}$$ contains a red copy of $$G_1$$ or a blue copy of $$G_2$$ , where r is the classical Ramsey number $$R(G_1,G_2)$$ and $$K_{r-1}\sqcup K_{1,k}$$ is the graph obtained from a $$K_{r-1}$$ and an additional vertex v by joining v to k vertices of $$K_{r-1}$$ . Let $$C_n$$ denote a cycle of order n and $$W_m$$ a wheel of order $$m+1$$ . Hook (2010) proved that $$r_*(C_n,W_3)=2n$$ for $$n\ge 5$$ . In this paper, it is shown that $$r_*(C_n,W_m)=2n$$ for m odd, $$n\ge m\ge 5$$ and $$n\ge 60$$ .

The Turan number ex(n, H) is the maximum number of edges in any graph of order n that contains no copy of H as a subgraph. For any three positive integers p, q, r with $$p\le q\le r$$ and $$q\ge 2$$ , let $$\theta (p,q,r)$$ denote the graph obtained from three internally disjoint paths with the same pair of endpoints, where the three paths are of lengths p, q, r, respectively. Let $$k=p+q+r-1$$ . In this paper, we obtain the exact value of $$ex(n,\theta (p,q,r))$$ and characterize the unique extremal graph for $$n\ge 9k^2-3k$$ and any p, q, r with different parities. This extends a known result on odd cycles.

Suppose that G is a finite group and X is a G-conjugacy classes of involutions. The commuting involution graph $${\mathcal {C}}(G,X)$$ C ( G , X ) is the graph whose vertex set is X with $$x, y \in X$$ x , y ∈ X being joined if $$x \ne y$$ x ≠ y and $$xy = yx$$ x y = y x . Here for various exceptional Lie type groups of characteristic two we investigate their commuting involution graphs.

Let $$T_{n}$$ be an arc-colored tournament of order n. The maximum monochromatic indegree $$\varDelta ^{-mon}(T_{n})$$ (resp. outdegree $$\varDelta ^{+mon}(T_{n})$$ ) of $$T_{n}$$ is the maximum number of in-arcs (resp. out-arcs) of a same color incident to a vertex of $$T_{n}$$ . The irregularity $$i(T_{n})$$ of $$T_{n}$$ is the maximum difference between the indegree and outdegree of a vertex of $$T_{n}$$ . A subdigraph H of an arc-colored digraph D is called rainbow if each pair of arcs in H have distinct colors. In this paper, we show that each vertex v in an arc-colored tournament $$T_{n}$$ with $$\varDelta ^{-mon}(T_n)\le \varDelta ^{+mon}(T_n)$$ is contained in at least $$\frac{\delta (v)(n-\delta (v)-i(T_n))}{2}-[\varDelta ^{-mon}(T_{n})(n-1)+\varDelta ^{+mon}(T_{n})d^+(v)]$$ rainbow triangles, where $$\delta (v)=\min \{d^+(v), d^-(v)\}$$ . We also give some maximum monochromatic degree conditions for $$T_{n}$$ to contain rainbow triangles, and to contain rainbow triangles passing through a given vertex. Finally, we present some examples showing that some of the conditions in our results are best possible.

A graphGis said to bek-vertex rigid in$$\mathbb {R}^d$$Rdif$$G-X$$G-Xis rigid in$$\mathbb {R}^d$$Rdfor all subsetsXof the vertex set ofGwith cardinality less thank. We determine the smallest number of edges in ak-vertex rigid graph onnvertices in$$\mathbb {R}^2$$R2, for all$$k\ge 4$$k≥4. We also considerk-edge-rigid graphs, defined by removing edges, as well ask-vertex globally rigid andk-edge globally rigid graphs in$$\mathbb {R}^d$$Rd. For$$d=2$$d=2we determine the corresponding tight bounds for each of these versions, for all$$k\ge 3$$k≥3. Our results complete the solutions of these extremal problems in the plane. The result onk-vertex rigidity verifies a conjecture of Kaszanitzky and Király (Graphs Combin, 32:225–240, 2016). We also determine the degree of vertex redundancy of powers of cycles, with respect to rigidity in the plane, answering a question of Yu and Anderson (Int J Robust Nonlinear Control, 19(13):1427–1446, 2009).

Extending some properties from the Euclidean plane to any normed plane, we show the validity of the Monma–Paterson–Suri–Yao algorithm for finding the maximum-weighted spanning tree of a set of n points, where the weight of an edge is the distance between the end points measured by the norm and there are not repeated distances. For strictly convex normed planes, we expose a strategy for moving slightly the points of the set in order to obtain distinct distances.

Colourful connection concepts in graph theory such as rainbow connection, proper connection, odd connection or conflict-free connection have received a lot of attention. For an integer $$k \ge 1$$ we call a path P in a graph G k-colourful, if at least k vertices of P are pairwise differently coloured. A graph G is k-colourful connected, if any two vertices of G are connected by a k-colouful path. Now we call the least integer k, which makes G k-colourful connected, the k-colourful connection number of G. In this paper, we introduce the (strong, internal) k-colourful connection number of a graph, establish bounds for our new invariants in several graph classes as well as compute exact values for $$k\in [3]$$ .

We give a survey on graphs with fixed smallest adjacency eigenvalue, especially on graphs with large minimal valency and also on graphs with good structures. Our survey mainly consists of the following two parts: At the end of the survey, we also discuss signed graphs with fixed smallest adjacency eigenvalue and present some new findings.

In this paper, we propose a new conjecture that the complete graph $$K_{4m+1}$$ can be decomposed into copies of two arbitrary trees, each of size $$m, m \ge 1$$ . To support this conjecture we prove that the complete graph $$K_{4cm+1}$$ can be decomposed into copies of an arbitrary tree with m edges and copies of the graph H, where H is either a path with m edges or a star with m edges and where c is any positive integer. Further, we discuss related open problems.

For a consecutive ordering of the edges of a graph $$G=(V,E)$$ , the point sum of a vertex is the sum of the indices of edges incident with that vertex. Motivated by questions of balancing accesses in data placements in the presence of popularity rankings, an edge ordering is egalitarian when all point sums are equal, and almost egalitarian when two point sums differ by at most 1. It is established herein that complete graphs on n vertices admit an egalitarian edge ordering when $$n \equiv 1,2,3 \pmod {4}$$ and $$n \not \in \{3,5\}$$ , or an almost egalitarian edge ordering when $$n \equiv 0 \pmod {4}$$ and $$n \ne 4$$ .

A dominating set of a graph is a subset D of the vertices such that every vertex not in D is adjacent to some vertex of D. In this paper, we introduce several variants of dominating sets in the square grid, periodic square grid and cylindric square grid by considering translation symmetry. We provide their exact enumerations in terms of domination polynomials. We also analyze the asymptotic behavior of the growth rates of their cardinality.

A 1-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing. Czap and Hudak showed that every 1-planar graph with n vertices has crossing number at most $$n-2$$ . In this paper, we prove that every maximal 1-planar graph G with n vertices has crossing number at most $$n-2-(2\lambda _1+2\lambda _2+\lambda _3)/6$$ , where $$\lambda _1$$ and $$\lambda _2$$ are respectively the numbers of 2-degree and 4-degree vertices in G, and $$\lambda _3$$ is the number of odd vertices w in G such that either $$d_G(w)\le 9$$ or $$G-w$$ is 2-connected. Furthermore, we show that every 3-connected maximal 1-planar graph with n vertices and m edges has crossing number $$m-3n+6$$ .

A finite subset of a Euclidean space is called an $s$-distance set if there exist exactly $s$ values of the Euclidean distances between two distinct points in the set. In this paper, we prove that the maximum cardinality among all 5-distance sets in $\mathbb{R}^3$ is 20, and every $5$-distance set in $\mathbb{R}^3$ with $20$ points is similar to the vertex set of a regular dodecahedron., Comment: 16 pages, 7 figures

A set S of vertices is a determining set of a graph G if every automorphism of G is uniquely determined by its action on S. The determining number of G, denoted by $$\mathrm{Det}(G)$$ , is the smallest size of a determining set. In this paper, we give an explicit characterization for connected graphs of order n with determining number $$n-3$$

Zarankiewicz’s conjecture states that the crossing number $$\text {cr}(K_{m,n})$$ of the complete bipartite graph $$K_{m,n}$$ is $$Z(m,n):=\lfloor \frac{m}{2}\rfloor \lfloor \frac{m-1}{2}\rfloor \lfloor \frac{n}{2}\rfloor \lfloor \frac{n-1}{2}\rfloor$$ , where $$\lfloor x \rfloor$$ denotes the largest integer no more than x. It is conjectured that the crossing number $$\text {cr}(K_{1,m,n})$$ of the complete tripartite graph $$K_{1,m,n}$$ is $$Z(m+1,n+1)-\lfloor \frac{m}{2}\rfloor \lfloor \frac{n}{2}\rfloor$$ . When one of m and n is even, Ho proved that this conjecture is true if Zarankiewicz’s conjecture holds, in 2008. When both m and n are odd, Ho proved that $$\text {cr}(K_{1,m,n})\ge \text {cr}(K_{m+1,n+1})-\left\lfloor \frac{n}{m}\lfloor \frac{m}{2}\rfloor \lfloor \frac{m+1}{2}\rfloor \right\rfloor$$ and conjectured that equality holds in this inequality. Which one of the conjectures may be true? In this paper, we proved that if Zarankiewicz’s conjecture holds, then the former one is true.

Let G be a connected irregular graph on n vertices with maximum degree $$\Delta $$ and diameter D. The spectral radius of G, which is denoted by $$\rho (G)$$ , is the largest eigenvalue of the adjacency matrix of G. In this paper, we study the lower bound of $$\Delta -\rho (G)$$ . As a result, a new lower bound is obtained which improves the known lower bounds of $$\Delta -\rho (G)$$ .

The concept of antimagic labelings of a graph is to produce distinct vertex sums by labeling edges through consecutive numbers starting from one. A long-standing conjecture is that every connected graph, except a single edge, is antimagic. Some graphs are known to be antimagic, but little has been known about sparse graphs, not even trees. This paper studies a weak version called $k$-shifted-antimagic labelings which allow the consecutive numbers starting from $k+1$, instead of starting from 1, where $k$ can be any integer. This paper establishes connections among various concepts proposed in the literature of antimagic labelings and extends previous results in three aspects: $\bullet$ Some classes of graphs, including trees and graphs whose vertices are of odd degrees, which have not been verified to be antimagic are shown to be $k$-shifted-antimagic for sufficiently large $k$. $\bullet$ Some graphs are proved $k$-shifted-antimagic for all $k$, while some are proved not for some particular $k$. $\bullet$ Disconnected graphs are also considered.

A path in an edge-colored graph is called a monochromatic path if all edges of the path have a same color. We call $k$ paths $P_1,\cdots,P_k$ rainbow monochromatic paths if every $P_i$ is monochromatic and for any two $i\neq j$, $P_i$ and $P_j$ have different colors. An edge-coloring of a graph $G$ is said to be a rainbow monochromatic $k$-edge-connection coloring (or $RMC_k$-coloring for short) if every two distinct vertices of $G$ are connected by at least $k$ rainbow monochromatic paths. We use $rmc_k(G)$ to denote the maximum number of colors that ensures $G$ has an $RMC_k$-coloring, and this number is called the rainbow monochromatic $k$-edge-connection number. We prove the existence of $RMC_k$-colorings of graphs, and then give some bounds of $rmc_k(G)$ and present some graphs whose $rmc_k(G)$ reaches the lower bound. We also obtain the threshold function for $rmc_k(G(n,p))\geq f(n)$, where $\lfloor\frac{n}{2}\rfloor> k\geq 1$., 22 pages

An edge-colored graph is called rainbow if all its edges are colored distinct. The anti-Ramsey number of a graph family $${\mathcal {F}}$$ in the graph G, denoted by $$AR{(G,{\mathcal {F}})}$$ , is the maximum number of colors in an edge-coloring of G without rainbow subgraph in $${\mathcal {F}}$$ . The anti-Ramsey number for the short cycle $$C_3$$ has been determined in a few graphs. Its anti-Ramsey number in the complete graph can be easily obtained from the lexical edge-coloring. Gorgol considered the problem in complete split graphs which contains complete graphs as a subclass. In this paper, we study the problem in the complete multipartite graph which further enlarges the family of complete split graphs. The anti-Ramsey numbers for $$C_3$$ and $$C_3^{+}$$ in complete multipartite graphs are determined. These results contain the known results for $$C_3$$ and $$C_3^{+}$$ in complete and complete split graphs as corollaries.

A graph G is said to be distance d matchable if, for any matching M of G in which edges are pairwise at least distance d apart, there exists a perfect matching $$M^*$$ of G which contains M. In this paper, we prove the following results: (i) if G is a cubic bipartite graph in which, for each $$e \in E(G)$$ , there exist two cycles $$C_1$$ , $$C_2$$ of length at most d such that $$E(C_1) \cap E(C_2) = \{e\}$$ , then G is distance $$d-1$$ matchable, and (ii) if G is a planar or projective planar cubic bipartite graph in which, for each $$e \in E(G)$$ , there exist two cycles $$C_1$$ , $$C_2$$ of length at most 6 such that $$e \in E(C_1) \cap E(C_2)$$ , then G is distance 6 matchable.

Given a bipartite cubic graph with a certain degree of symmetry two covering constructions that provide infinitely many tetravalent graphs admitting half-arc-transitive groups of automorphisms are introduced. Symmetry properties of constructed graphs are investigated. In the second part of the paper the two constructions are applied to the Heawood graph, the well-known incidence graph of the Fano plane.

Let $$D=(V,A)$$ D = ( V , A ) be a digraph of order n, S a subset of V of size k and $$2\le k\le n$$ 2 ≤ k ≤ n . A strong subgraph H of D is called an S-strong subgraph if $$S\subseteq V(H)$$ S ⊆ V ( H ) . A pair of S-strong subgraphs $$D_1$$ D 1 and $$D_2$$ D 2 are said to be arc-disjoint if $$A(D_1)\cap A(D_2)=\emptyset$$ A ( D 1 ) ∩ A ( D 2 ) = ∅ . A pair of arc-disjoint S-strong subgraphs $$D_1$$ D 1 and $$D_2$$ D 2 are said to be internally disjoint if $$V(D_1)\cap V(D_2)=S$$ V ( D 1 ) ∩ V ( D 2 ) = S . Let $$\kappa _S(D)$$ κ S ( D ) (resp. $$\lambda _S(D)$$ λ S ( D ) ) be the maximum number of internally disjoint (resp. arc-disjoint) S-strong subgraphs in D. The strong subgraphk-connectivity is defined as $$\begin{aligned} \kappa _k(D)=\min \{\kappa _S(D)\mid S\subseteq V, |S|=k\}. \end{aligned}$$ κ k ( D ) = min { κ S ( D ) ∣ S ⊆ V , | S | = k } . As a natural counterpart of the strong subgraph k-connectivity, we introduce the concept of strong subgraphk-arc-connectivity which is defined as $$\begin{aligned} \lambda _k(D)=\min \{\lambda _S(D)\mid S\subseteq V(D), |S|=k\}. \end{aligned}$$ λ k ( D ) = min { λ S ( D ) ∣ S ⊆ V ( D ) , | S | = k } . A digraph $$D=(V, A)$$ D = ( V , A ) is called minimally strong subgraph$$(k,\ell )$$ ( k , ℓ ) -(arc-)connected if $$\kappa _k(D)\ge \ell$$ κ k ( D ) ≥ ℓ (resp. $$\lambda _k(D)\ge \ell$$ λ k ( D ) ≥ ℓ ) but for any arc $$e\in A$$ e ∈ A , $$\kappa _k(D-e)\le \ell -1$$ κ k ( D - e ) ≤ ℓ - 1 (resp. $$\lambda _k(D-e)\le \ell -1$$ λ k ( D - e ) ≤ ℓ - 1 ). In this paper, we first give complexity results for $$\lambda _k(D)$$ λ k ( D ) , then obtain some sharp bounds for the parameters $$\kappa _k(D)$$ κ k ( D ) and $$\lambda _k(D)$$ λ k ( D ) . Finally, minimally strong subgraph $$(k,\ell )$$ ( k , ℓ ) -connected digraphs and minimally strong subgraph $$(k,\ell )$$ ( k , ℓ ) -arc-connected digraphs are studied.

Let $$\varDelta$$ be a digraph of diameter 2 with the maximum undirected vertex degree t and the maximum directed out-degree z. The largest possible number v of vertices of $$\varDelta$$ is given by the following generalization of the Moore bound: $$\begin{aligned} v\le (z+t)^2+z+1, \end{aligned}$$ and a digraph attaining this bound is called a Moore digraph. Apart from the case $$t=1$$ , only three Moore digraphs are known, which are also Cayley graphs. Using computer search, Erskine (J Interconnect Netw, 17: 1741010, 2017) ruled out the existence of further examples of Cayley digraphs attaining the Moore bound for all orders up to 485. We use an algebraic approach to this problem, which goes back to an idea of G. Higman from the theory of association schemes, also known as Benson’s Lemma in finite geometry, and show non-existence of Moore Cayley digraphs of certain orders.

The Turan number for a graph H, denoted by $$\text {ex}(n,H)$$ , is the maximum number of edges in any simple graph with n vertices which doesn’t contain H as a subgraph. In this paper we find the lower and upper bounds for $$\text { ex}(n,W_{2t+1})$$ . We show that if $$n\ge 4t$$ , then $$\text { ex}(n,W_{2t+1})\ge \left\lfloor \lfloor \frac{2n+t}{4}\rfloor (n+\frac{t-1}{2}-\lfloor \frac{2n+t}{4}\rfloor )\right\rfloor +1.$$ We also show that for sufficiently large n and $$t\ge 5$$ , $$\text { ex}(n,W_{2t+1})\le \frac{ n^2 }{4}+{t-1\over 2}n$$ . Moreover we find the exact value of the Turan number for $$W_9$$ . That is, we show that for sufficiently large n, $$\text { ex}(n,W_9)= \lfloor \frac{n^2}{4}\rfloor +\lceil \frac{3}{4}n\rceil +1$$ .

Let $$\alpha \ge 0$$ and $$k \ge 2$$ be integers. For a graph G, the total k-excess of G is defined as $$\text{ te }(G;k)=\sum _{v \in V(G)}\max \{d_G(v)-k,0\}$$ . In this paper, we propose a new closure concept for a spanning tree with bounded total k-excess. We prove that: Let G be a connected graph, and let u and v be two non-adjacent vertices of G. If G satisfies one of the following conditions, then G has a spanning tree T such that $$\text{ te }(T;k) \le \alpha$$ if and only if $$G+uv$$ has a spanning tree $$T'$$ such that $$\text{ te }(T';k) \le \alpha$$ : We also show examples to show that these conditions are sharp.

Victoir (2004) developes a powerful method for constructing high-dimensional cubature formulas with small number of points, which consists of the corner-vector approach for the hyperoctahedral group $$B_d$$ and the thinning approach based on orthogonal arrays and combinatorial designs. Hirao et al. (2014) applies this to constructions of optimal rotatable designs on the d-dimensional unit ball $${\varvec{B}}^d$$ and thereby finds some infinite series of third-order designs with small number of points. Afterwards, Sawa and Hirao (2017) discusses the corner-vector approach for group $$D_d$$ that can be realized as the symmetry group of a demihypercube in $${\mathbb {R}}^d$$ . In the present paper we discuss a further generalization and improvement of these works, and describe many examples and infinite series of D-optimal rotatable designs with small number of points. The core and novelty in the presentation lies in the focus on the cubature theory in numerical analysis or Euclidean design theory in combinatorics, which not only improves and/or generalizes previous works in those fields of mathematics but also provides a unified mathematical description of various classes of factorial designs, including Box–Hunter solid designs, Box–Behnken designs, central composite designs and Plackett–Burman designs, in the modern framework of the cubature theory. Our new framework enables one, for example, to briefly evaluate the maximum integer t for which such classical factorial designs are of t-th order rotatable.

For a set L of positive integers, a set system $${\mathcal F}\subseteq 2^{[n]}$$ F ⊆ 2 [ n ] is said to be L-close Sperner, if for any pair F, G of distinct sets in $${\mathcal F}$$ F the skew distance $$sd(F,G)=\min \{|F\setminus G|,|G\setminus F|\}$$ s d ( F , G ) = min { | F \ G | , | G \ F | } belongs to L. We reprove an extremal result of Boros, Gurvich, and Milanič on the maximum size of L-close Sperner set systems for $$L=\{1\}$$ L = { 1 } , generalize it to $$|L|=1$$ | L | = 1 , and obtain slightly weaker bounds for arbitrary L. We also consider the problem when L might include 0 and reprove a theorem of Frankl, Füredi, and Pach on the size of largest set systems with all skew distances belonging to $$L=\{0,1\}$$ L = { 0 , 1 } .

For a fixed positive integer n and an r-uniform hypergraph H, the Turan number ex(n, H) is the maximum number of edges in an H-free r-uniform hypergraph on n vertices, and the Lagrangian density of H is defined as $$\pi _{\lambda }(H)=\sup \{r! \lambda (G) : G \;\text {is an}\; H\text {-free} \;r\text {-uniform hypergraph}\}$$ , where $$\lambda (G)=\max \{\sum _{e \in G}\prod \limits _{i\in e}x_{i}: x_i\ge 0 \;\text {and}\; \sum _{i\in V(G)} x_i=1\}$$ is the Lagrangian of G. For an r-uniform hypergraph H on t vertices, it is clear that $$\pi _{\lambda }(H)\ge r!\lambda {(K_{t-1}^r)}$$ . Let us say that an r-uniform hypergraph H on t vertices is $$\lambda $$ -perfect if $$\pi _{\lambda }(H)= r!\lambda {(K_{t-1}^r)}$$ . A result of Motzkin and Straus implies that all graphs are $$\lambda $$ -perfect. It is interesting to explore what kind of hypergraphs are $$\lambda $$ -perfect. A conjecture in [22] proposes that every sufficiently large r-uniform linear hypergraph is $$\lambda $$ -perfect. In this paper, we investigate whether the conjecture holds for linear 3-uniform paths. Let $$P_t=\{e_1, e_2, \dots , e_t\}$$ be the linear 3-uniform path of length t, that is, $$|e_i|=3$$ , $$|e_i \cap e_{i+1}|=1$$ and $$e_i \cap e_j=\emptyset $$ if $$|i-j|\ge 2$$ . We show that $$P_3$$ and $$P_4$$ are $$\lambda $$ -perfect. Applying the results on Lagrangian densities, we determine the Turan numbers of their extensions.

Let M and N be 3-connected matroids; we say that M is N-critical if M has an N-minor, but for each $$x\in E(M)$$ , $$M\backslash x$$ is not 3-connected or $$M\backslash x$$ has no N-minor. We establish that if M is an N-critical matroid with $$r^*(M)>\max \{3,r^*(N)\}$$ , then M has an element x such that either $$\mathrm{co}(M\backslash x)$$ is N-critical or M has a coline $$L^*$$ with $$|L^*|\ge 3$$ such that $$M\backslash L^*$$ is N-critical. As a corollary we get a chain theorem for the class of minimally 3-connected matroids. This chain theorem generalizes a previous one of Anderson and Wu for binary matroids.

Let G and H be finite undirected graphs. The Ramsey number R(G, H) is the smallest integer n such that for every graph F of order n, either F contains a subgraph isomorphic to G or its complement $${\overline{F}}$$ contains a subgraph isomorphic to H. An (s, t)-graph is a graph that contains neither a clique of order s nor an independent set of order t. In this paper we obtain some inequalities involving Ramsey numbers of the form $$R(K_4-e,K_t)$$ . In particular, a constructive proof implies that if G is a $$(k,s+1)$$ -graph, H is a $$(k,t+1)$$ -graph, and both G and H contain a $$(K_k-e)$$ -free graph M as an induced subgraph, then we have $$R(K_{k+1}-e,K_ {s+t+1}) > |V(G)| + |V(H)| + |V(M)|.$$ Furthermore, if $$s \le t$$ , then $$R(K_4-e,K_ {s+t+1}) \ge R(3,s+1)+R(3,t+1)+s$$ . In the experimental part, we use the $$(K_4-e)$$ -free graph generation process to construct graphs witnessing lower bounds for $$R(K_4-e,K_t)$$ , and compare the results obtained by this approach to the results obtained by analogous triangle-free process. Finally, some open problems involving Ramsey numbers of the form $$R(K_4-e,K_t)$$ and their asymptotics are posed.

In this paper, we enumerate the set of ordered trees with n edges according to the number of weakly protected points. Explicit formulas as well as generating functions are obtained. We also find that, as n goes to infinity, the proportion of weakly protected points among all vertices of ordered trees with n edges approaches 1/3.

The signature s(G) of a graph G is defined as the difference between its positive inertia index and negative inertia index. In 2013, Ma et al. conjectured that $$-c_3(G)\le s(G) \le c_5(G)$$ for an arbitrary simple graph G, where $$c_3(G)$$ denotes the number of cycles in G of length 3 modulo 4, $$c_5(G)$$ denotes the number of cycles in G of length 1 modulo 4. In this paper, we give some inequalities of signature of graphs, as applications, we prove that this conjecture holds for chordal graphs and cographs.

A graph is maximal k-degenerate if each induced subgraph has a vertex of degree at most k and adding any new edge to the graph violates this condition. In this paper, we provide sharp lower and upper bounds on Wiener indices of maximal k-degenerate graphs of order $$n \ge k \ge 1$$ . A graph is chordal if every induced cycle in the graph is a triangle and chordal maximal k-degenerate graphs of order $$n \ge k$$ are k-trees. For k-trees of order $$n \ge 2k+2$$ , we characterize all extremal graphs for the upper bound.

The first part of the paper studies star-cycle factors of graphs. It characterizes star-cycle factors of a graph $G$ and proves upper bounds for the minimum number of $K_{1,2}$-components in a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of a graph $G$. Furthermore, it shows where these components are located with respect to the Gallai-Edmonds decomposition of $G$ and it characterizes the edges which are not contained in any $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor of $G$. The second part of the paper proves that every edge-chromatic critical graph $G$ has a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor, and the number of $K_{1,2}$-components is bounded in terms of its fractional matching number. Furthermore, it shows that for every edge $e$ of $G$, there is a $\{K_{1,1}, K_{1,2}, C_n\colon n\ge 3\}$-factor $F$ with $e \in E(F)$. Consequences of these results for Vizing's critical graph conjectures are discussed., final version, 23 pages

It was conjectured by Koh and Tay [Graphs Combin. 18(4) (2002), 745–756] that for $$n\ge 5$$ every simple graph of order n and size at least $$\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n+5$$ has an orientation of diameter two. We prove this conjecture and hence determine for every $$n\ge 5$$ the minimum value of m such that every graph of order n and size m has an orientation of diameter two.

A weak coloring of a graph G embedded on a surface is a vertex coloring of G such that no face is monochromatic. The weak chromatic number of G is the minimum number k such that G has a weak k-coloring. Kundgen and Ramamurthi (J Combin Theory Ser B 85, 307–337, 2002) conjectured that for each positive integer k, there is a graph that has two different embeddings on the same surface whose weak chromatic numbers differ by at least k. In this paper, we answer this conjecture affirmatively in two ways.

Let $$r(K_{p,q},t)$$ be the maximum number of colors in an edge-coloring of the complete bipartite graph $$K_{p,q}$$ not having t edge-disjoint rainbow spanning trees. We prove that $$r(K_{p,p},1)=p^2-2p+2$$ for $$p\ge 4$$ and $$r(K_{p,q},1)=pq-2q+1$$ for $$p>q\ge 4$$ . Let $$t\ge 2$$ . We also show that $$r(K_{p,p},t)=p^2-2p+t+1$$ for $$p \ge 2t+\sqrt{3t-3}+4$$ and $$r(K_{p,q},t)=pq-2q+t$$ for $$p > q \ge 2t+\sqrt{3t-2}+4$$ .

A proper edge coloring of a graph G is strict neighbor-distinguishing if for any two adjacent vertices u and v, the set of colors used on the edges incident to u and the set of colors used on the edges incident to v are not included with each other. The strict neighbor-distinguishing index of G is the minimum number $$\chi '_\mathrm{snd}(G)$$ of colors in a strict neighbor-distinguishing edge coloring of G. In this paper, we prove that every connected subcubic graph G with $$\delta (G)\ge 2$$ has $$\chi '_\mathrm{snd}(G)\le 7$$ , and moreover $$\chi '_\mathrm{snd}(G)=7$$ if and only if G is a graph obtained from the graph $$K_{2,3}$$ by inserting a 2-vertex into one edge.

A clique of a graph G is a set of pairwise adjacent vertices of G. A clique-coloring of G is an assignment of colors to the vertices of G in such a way that no inclusion-wise maximal clique of size at least two of G is monochromatic. An equitable clique-coloring of G is a clique-coloring such that any two color classes differ in size by at most one. Bacso and Tuza proved that connected claw-free graphs with maximum degree at most four, other than chordless odd cycles of order greater than three, are 2-clique-colorable and a 2-clique-coloring can be found in $$O(n^{2})$$ Bacso and Tuza (Discrete Math Theor Comput Sci 11(2):15–24, 2009). In this paper we prove that every connected claw-free graph with maximum degree at most four, not a chordless odd cycle of order greater than three, has an equitable 2-clique-coloring. In addition we improve the algorithm described in the paper mentioned by giving an equitable 2-clique-coloring in linear time for this class of graphs.

A graph G is $$\ell $$ -distance-balanced if for each pair of vertices x and y at a distance $$\ell $$ in G, the number of vertices closer to x than to y is equal to the number of vertices closer to y than to x. A complete characterization of $$\ell $$ -distance-balanced corona products is given and characterization of lexicographic products for $$\ell \ge 3$$ , thus complementing known results for $$\ell \in \{1,2\}$$ and correcting an earlier related assertion. A sufficient condition on H which guarantees that $$K_n\,\square \,H$$ is $$\ell $$ -distance-balanced is given, and it is proved that if $$K_n\,\square \,H$$ is $$\ell $$ -distance-balanced, then H is an $$\ell $$ -distance-balanced graph. A known characterization of 1-distance-balanced graphs is extended to $$\ell $$ -distance-balanced graphs, again correcting an earlier claimed assertion.

In our work, we define a k-tuple of positive integers $$(x_1, \ldots , x_k)$$ to be a $$\chi $$ -sequence if there exists a k-chromatic graph G such that for each $$i \in \{1, \ldots , k\}$$ , the order of a minimum i-chromatic subgraph of G is equal to $$x_i$$ . Denote by $$\mathcal {X}_k$$ the set of all $$\chi $$ -sequences of length k. A very difficult question is to determine, for a given $$(x_1, \ldots , x_k) \in \mathcal {X}_k$$ , the set of all integers y such that $$(x_1, \ldots , x_k, y) \in \mathcal {X}_{k+1}$$ . We propose a few variants of this question and elaborate upon a number of partial results along the way.

In this paper we show that for each sufficiently large n there exist graphs G of order n and diameter 2 whose total domination number $$\gamma _t(G)$$ is greater than $$\sqrt{(3n\log n)/8}-\sqrt{n}$$ . On the other hand, it is shown that the total domination number of a graph of order $$n \geqslant 3$$ and diameter 2 is always less than $$\sqrt{(n\log n)/2}+\sqrt{n/2}$$ .