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.

Let F(G) be the number of forests of a graph G. Similarly let C(G) be the number of connected spanning subgraphs of a connected graph G. We bound F(G) and C(G) for regular graphs and for graphs with a fixed average degree. Among many other things we study $$f_d=\sup _{G\in {\mathcal {G}}_d}F(G)^{1/v(G)}$$ f d = sup G ∈ G d F ( G ) 1 / v ( G ) , where $${\mathcal {G}}_d$$ G d is the family of d-regular graphs, and v(G) denotes the number of vertices of a graph G. We show that $$f_3=2^{3/2}$$ f 3 = 2 3 / 2 , and if $$(G_n)_n$$ ( G n ) n is a sequence of 3-regular graphs with the length of the shortest cycle tending to infinity, then $$\lim _{n\rightarrow \infty }F(G_n)^{1/v(G_n)}=2^{3/2}$$ lim n → ∞ F ( G n ) 1 / v ( G n ) = 2 3 / 2 . We also improve on the previous best bounds on $$f_d$$ f d for $$4\le d\le 9$$ 4 ≤ d ≤ 9 .

Let G be a graph and k an integer with $$2\le k\le n$$ . The k -tree-connectivity of G, denoted by $$\kappa _k(G)$$ , is defined as the minimum $$\kappa _G(S)$$ over all k-subsets S of vertices, where $$\kappa _G(S)$$ denotes the maximum number of internally disjoint S-trees in G. The k -path-connectivity of G, denoted by $$\pi _k(G)$$ , is defined as the minimum $$\pi _G(S)$$ over all k-subsets S of vertices, where $$\pi _G(S)$$ denotes the maximum number of internally disjoint S-paths in G. In this paper, we first prove that for any fixed integer $$k\ge 1$$ , given a graph G and a subset S of V(G), deciding whether $$\pi _G(S)\ge k$$ is $$\mathcal {NP}$$ -complete. Moreover, we also show that for any fixed integer $$k_1\ge 5$$ , given a graph G, a $$k_1$$ -subset S of V(G) and an integer $$1\le k_2\le n-1$$ , deciding whether $$\pi _G(S)\ge k_2$$ is $$\mathcal {NP}$$ -complete. Let $$\pi (k,\ell )=1+\max \{\kappa (G)|\ $$ G $$\text {\ is\ a\ graph\ with}\ \pi _k(G)< \ell \}$$ . Hager (Discrete Math 59:53–59, 1986) showed that $$\ell (k-1)\le \pi (k,\ell )\le 2^{k-2}\ell$$ and conjectured that $$\pi (k,\ell )=\ell (k-1)$$ for $$k\ge 2$$ and $$\ell \ge 1$$ . He also confirmed the conjecture for $$2\le k\le 4$$ and proved $$\pi (5,\ell )\le \lceil \frac{9}{2}\ell \rceil$$ . By introducing a “Generalized Path-Bundle Transformation”, we confirm the conjecture for $$k=5$$ and prove that $$\pi (k,\ell )\le 2^{k-3}\ell$$ for $$k\ge 5$$ and $$\ell \ge 1$$ . By employing this transformation, we also prove that if G is a graph with $$\kappa (G)\ge (k-1)\ell$$ for any $$k\ge 2$$ and $$\ell \ge 1$$ , then $$\kappa _k(G)\ge \ell$$ .

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. It was conjectured that every simple graph G with maximum degree $$\Delta $$ is acyclically edge- $$(\Delta +2)$$ -colorable. In this paper, we confirm the conjecture for chordal graphs G with $$\Delta \le 6$$ .

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.

An edge-girth-regular $$egr(v,k,g,\lambda )$$ -graph $$\Gamma $$ is a k-regular graph of order v and girth g in which every edge is contained in $$\lambda $$ distinct g-cycles. Edge-girth-regularity is shared by several interesting classes of graphs which include edge- and arc-transitive graphs, Moore graphs, as well as many of the extremal k-regular graphs of prescribed girth or diameter. Infinitely many $$egr(v,k,g,\lambda )$$ -graphs are known to exist for sufficiently large parameters $$(k,g,\lambda )$$ , and in line with the well-known Cage Problem we attempt to determine the smallest graphs among all edge-girth-regular graphs for given parameters $$(k,g,\lambda )$$ . To facilitate the search for $$egr(v,k,g,\lambda )$$ -graphs of the smallest possible orders, we derive lower bounds in terms of the parameters k, g and $$\lambda $$ . We also determine the orders of the smallest $$egr(v,k,g,\lambda )$$ -graphs for some specific parameters $$(k,g,\lambda )$$ , and address the problem of the smallest possible orders of bipartite edge-girth-regular graphs.

For a graph G, define $$\sigma _2(G)$$ by $$\sigma _2(G)=\min \bigl \{d_G(x)+d_G(y):x, y\in V(G), x\ne y, xy\notin E(G)\bigr \}$$ . If G is a bipartite graph with partite sets X and Y, we also define $$\sigma _{1,1}(G)$$ by $$\sigma _{1,1}(G)=\min \{d_G(x)+d_G(y):x\in X, y\in Y, xy\notin E(G)\}$$ . Ore’s theorem states that a graph of order $$n\ge 3$$ with $$\sigma _2(G)\ge n$$ contains a hamiltonian cycle and the Moon–Moser theorem states that a balanced bipartite graph G of order $$2n\ge 4$$ with $$\sigma _{1,1}(G)\ge n+1$$ contains a hamiltonian cycle. In Chen et al. (Discrete Math 343:Article No. 111663, 2020), we studied the relationship between Ore’s theorem and the Moon–Moser theorem, and proved that the refinement of the Moon–Moser theorem given by Ferrara et al. (Discrete Math 312:459–461, 2012) implies Ore’s theorem for graphs of even order. In this paper, we extend the above study to the graphs of odd order. Since no graphs of odd order contain a spanning balanced bipartite subgraph, the Moon–Moser theorem does not work in this case. We instead introduce its counterpart for the graphs in which the orders of the partite sets differ by 1, proved in Matsubara et al. (Discrete Math 340:87–95, 2017). We refine this result and prove that this refinement implies Ore’s theorem.

The crossing number of a graph G, denoted by cr(G), is defined as the smallest possible number of edge-crossings in a drawing of G in the plane. The cone CG, obtained from G by adding a new vertex adjacent to all the vertices in G. Let $$\phi _\mathrm {s}(k)=\min \{cr(CG)-cr(G)\}$$ , where the minimum is taken over all the simple graphs G with crossing number k. Alfaro et al. (SIAM J Discrete Math, 32: 2080–2093, 2018) determined $$\phi _\mathrm {s}(k)\le k$$ for $$k\ge 3$$ , and proved $$\phi _\mathrm {s}(3)=3$$ , $$\phi _\mathrm {s}(4)=4$$ and $$\phi _\mathrm {s}(5)=5$$ . In this work, we improve the upper bound for $$\phi _\mathrm {s}(k)$$ and our main result includes the following, slightly surprising, fact: $$\phi _\mathrm {s}(6)=5$$ and $$\phi _\mathrm {s}(7)=6$$ .

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.

Let $$\mathrm{pr}(K_{n}, G)$$ pr ( K n , G ) be the maximum number of colors in an edge-coloring of $$K_{n}$$ K n with no properly colored copy of G. For a family $${\mathcal {F}}$$ F of graphs, let $$\mathrm{ex}(n, {\mathcal {F}})$$ ex ( n , F ) be the maximum number of edges in a graph G on n vertices which does not contain any graphs in $${\mathcal {F}}$$ F as subgraphs. In this paper, we show that $$\mathrm{pr}(K_{n}, G)-\mathrm{ex}(n, \mathcal {G'})=o(n^{2}), $$ pr ( K n , G ) - ex ( n , G ′ ) = o ( n 2 ) , where $$\mathcal {G'}=\{G-M: M \text { is a matching of }G\}$$ G ′ = { G - M : M is a matching of G } . Furthermore, we determine the value of $$\mathrm{pr}(K_{n}, P_{l})$$ pr ( K n , P l ) for sufficiently large n and the exact value of $$\mathrm{pr}(K_{n}, G)$$ pr ( K n , G ) , where G is $$C_{5}, C_{6}$$ C 5 , C 6 and $$K_{4}^{-}$$ K 4 - , respectively. Also, we give an upper bound and a lower bound of $$\mathrm{pr}(K_{n}, K_{2,3})$$ pr ( K n , K 2 , 3 ) .

Let G be a graph that may have multiedges, let $$\mu (u, v)$$ denote the number of edges joining u and v in G, and let $$\mu (u)=\max _{v\in N(u)} \mu (u, v)$$ . Let $$a, b:V(G)\ \longrightarrow {\mathbb {N}}{\setminus }\{0,1\}$$ be two functions with $$d_G(v)\ge a(v)+b(v)+2\mu (v)-3$$ for each $$v\in V(G)$$ . We show that, if G does not contain $$C_4$$ , then G admits a partition (A, B) with $$d_{G[A]}(u)\ge a(u)$$ for each $$u\in A$$ , and $$d_{G[B]}(v)\ge b(v)$$ for each $$v\in B$$ . This generalizes a theorem of Ma and Yang on simple graphs, and answers a question of Schweser and Stiebitz.

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.

An edge-coloured graph G is called conflict-free connected if every two distinct vertices are connected by at least one path, which contains a colour used on exactly one of its edges. The conflict-free connection number of a connected graph G, denoted by cfc(G), is the smallest number of colours needed in order to make it conflict-free connected. For a graph G, let C(G) be the subgraph of G induced by its set of bridges. Our main results are the following: (1) Let $$k\ge 2$$ and G be a connected graph of order n containing bridges. If $$\vert E(G)\vert \ge {{n-2k}\atopwithdelims ()2}+2k+1$$ , then $$cfc(G)\le k$$ or $$\varDelta (C(G)) \ge k+1.$$ (2) Let G be a connected graph of order n with $$t \ge 4$$ bridges such that $$n \ge t+15.$$ If $$\vert E(G)\vert \ge {{n-t-2}\atopwithdelims ()2}+t+4$$ , then $$cfc(G)=2$$ or G belongs to a class of exceptional graphs.

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.

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]$$ .

Motivated by several conjectures due to Nikoghosyan, in a recent article due to Li et al., the aim was to characterize all possible graphs H such that every 1-tough H-free graph is hamiltonian. The almost complete answer was given there by the conclusion that every proper induced subgraph H of $$K_1\cup P_4$$ K 1 ∪ P 4 can act as a forbidden subgraph to ensure that every 1-tough H-free graph is hamiltonian, and that there is no other forbidden subgraph with this property, except possibly for the graph $$K_1\cup P_4$$ K 1 ∪ P 4 itself. The hamiltonicity of 1-tough $$K_1\cup P_4$$ K 1 ∪ P 4 -free graphs, as conjectured by Nikoghosyan, was left there as an open case. In this paper, we consider the stronger property of pancyclicity under the same condition. We find that the results are completely analogous to the hamiltonian case: every graph H such that any 1-tough H-free graph is hamiltonian also ensures that every 1-tough H-free graph is pancyclic, except for a few specific classes of graphs. Moreover, there is no other forbidden subgraph having this property. With respect to the open case for hamiltonicity of 1-tough $$K_1\cup P_4$$ K 1 ∪ P 4 -free graphs we give infinite families of graphs that are not pancyclic.

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 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$$

For an even graph G and non-negative integers r and s, the pair $$(r,\,s)$$ is an admissible pair if $$4r+8s=|E(G)|.$$ If G admits a decomposition into r copies of $$C_4,$$ the cycle of length four, and s copies of $$C_8,$$ the cycle of length eight, for every admissible pair $$(r,\,s),$$ then G has a $$\{C_4^r,\,C_8^s\}$$ -decomposition. In this paper, a necessary and sufficient condition is obtained for the existence of a $$\{C_4^r,\,C_8^s\}$$ -decomposition of the complete k-partite graph $$K_{a_1,\,a_2,\,\dots ,\,a_k},$$ where $$k\ge 3.$$ Further, a characterization is obtained for the graph $$K_m\times K_n,$$ where $$\times$$ denotes the tensor product of graphs, to admit a $$\{C_4^r,\,C_8^s\}$$ -decomposition.

Let G be an irregular graph on n vertices with maximum degree $$\Delta \ge 3$$ and diameter $$D\ge 3$$ . The spectral radius of G, which is denoted by $$\rho (G)$$ , is the largest eigenvalue of the adjacency matrix of G. In this paper, a new lower bound of $$\Delta -\rho (G)$$ is given, which improves the previous bounds intrinsically.

It is well known that a graph is bipartite if and only if it contains no odd cycles. Gallai characterized edge colorings of complete graphs containing no properly colored triangles in recursive sense. In this paper, we completely characterize edge-colored complete graphs containing no properly colored odd cycles and give an efficient algorithm with complexity $$O(n^{3})$$ for deciding the existence of properly colored odd cycles in an edge-colored complete graph of order n. Moreover, we show that for two integers k, m with $$m\geqslant k\geqslant 3$$ , where $$k-1$$ and m are relatively prime, an edge-colored complete graph contains a properly colored cycle of length $$\ell \equiv k\ (\text{mod}\ m)$$ if and only if it contains a properly cycle of length $$\ell '\equiv k\ (\text{mod }\ m)$$ , where $$\ell '< 2m^{2}(k-1)+3m$$ .

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.

In combinatorics, a latin square is a $n\times n$ matrix filled with n different symbols, each occurring exactly once in each row and exactly once in each column. Associated to each latin square, we can define a simple graph called a latin square graph. In this article, we compute lower and upper bounds for the domination number and the k-tuple total domination numbers of such graphs. Moreover, we describe a formula for the 2-tuple total domination number., To appear in Graphs and Combinatorics

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.

Let G be a simple graph of order $$n\ge 2$$ and let $$k\in \{1,\ldots ,n-1\}$$ . The k-token graph $$F_k(G)$$ of G is the graph whose vertices are the k-subsets of V(G), where two vertices are adjacent in $$F_k(G)$$ whenever their symmetric difference is an edge of G. In 2018 Leanos and Trujillo-Negrete proved that if G is t-connected and $$t\ge k$$ , then $$F_k(G)$$ is at least $$k(t-k+1)$$ -connected. In this paper we show that such a lower bound remains true in the context of edge-connectivity. Specifically, we show that if G is t-edge-connected and $$t\ge k$$ , then $$F_k(G)$$ is at least $$k(t-k+1)$$ -edge-connected. We also provide some families of graphs attaining this bound.

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.

This paper deals with the vertex connectivity of enhanced power graphs of finite groups. We classify all abelian groups G such that the vertex connectivity of enhanced power graph of G is 1. We derive an upper bound for the vertex connectivity of the enhanced power graph of any general abelian group G. Also we completely characterize all abelian groups G, such that the proper enhanced power graph is connected. Moreover, we study some special class of non-abelian groups G such that the proper enhanced power graph is connected and we find their vertex connectivity.

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.

The $k$-independence number of a graph $G$ is the maximum size of a set of vertices at pairwise distance greater than $k$. In this paper, for each positive integer $k$, we prove sharp upper bounds for the $k$-independence number in an $n$-vertex connected graph with given minimum and maximum degree., Comment: 16 pages, 11 figures

The acyclic chromatic number a(G) of a graph G is the minimum number of colors such that G has a proper vertex coloring and no bichromatic cycles. For a graph G with maximum degree $$\Delta $$ , Grunbaum (1973) conjectured $$a(G)\le \Delta +1$$ . Up to now, the conjecture has only been shown for $$\Delta \le 4$$ . In this paper, it is proved that $$a(G)\le 12$$ for $$\Delta =7$$ , thus improving the result $$a(G)\le 17$$ of Dieng et al. (in: Proc. European conference on combinatorics, graph theory and applications, 2010).

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.