Search

A leaf of a tree is a vertex of degree one and a branch vertex of a tree is a vertex of degree strictly greater than two. This paper shows two degree conditions for graphs to have spanning trees with total bounded number of branch vertices and leaves. Moreover, the sharpness of our results is shown. [ABSTRACT FROM AUTHOR]

A graph is called edge-primitive if its automorphism group acts primitively on its edge-set. In this paper, edge-primitive graphs of prime power order are determined. [ABSTRACT FROM AUTHOR]

The Turán type extremal problems ask to maximize the number of edges over all graphs which do not contain fixed subgraphs. Similarly, their spectral counterparts ask to maximize spectral radius of all graphs which do not contain fixed subgraphs. In this paper, we determine the maximum spectral radius of all graphs without a linear forest as a subgraph and all the extremal graphs. In addition, the maximum number of edges and spectral radius of all bipartite graphs without k·P3 as a subgraph are obtained and all the extremal graphs are also determined. Moreover, some relations between Turán type extremal problems and their spectral counterparts are discussed. [ABSTRACT FROM AUTHOR]

For two given graphs G1 and G2, the Ramsey number R(G1,G2) is the smallest integer n such that for any graph G of order n, either G contains G1 or its complement G¯ contains G2. Let Pn,Sn and Tn denote a path, a star and a tree of order n, respectively. A generalized wheel, denoted by Ws,m, is the join of a complete graph Ks and a cycle Cm. In this paper, we show that R(Tn,Ws,4)=(n-1)(s+1)+1 for n≥3,s≥2 and R(Tn,Ws,5)=(n-1)(s+2)+1 for n≥3,s≥1. These generalize some known results on Ramsey numbers for a tree versus a wheel. [ABSTRACT FROM AUTHOR]

Let Fq be the field of size q and SL(n, q) be the special linear group of order n over the field Fq. Assume that n is an even integer. Let Ai⊆SL(n,q) for i=1,2,⋯,k and |A1|=|A2|=⋯=|Ak|=l. The set {A1,A2,⋯,Ak} is called a k-cross (n, q)-Parsons set of size l, if for any pair of (i, j) with i≠j, A-B∈SL(n,q) for all A∈Ai and B∈Aj. Let m(k, n, q) be the largest integer l for which there is a k-cross (n, q)-Parsons set of size l. The integer m(k, n, q) will be called the k-cross (n, q)-Parsons numbers. In this paper, we will show that m(3,2,q)≤q. Furthermore, m(3,2,q)=q if and only if q=4r for some positive integer r. We will also show that if n is a multiple of q-1, then m(q-1,n,q)≥q12n(n-1). [ABSTRACT FROM AUTHOR]

This paper studies the connectivity and biconnectivity of coloring graphs. For k∈N, the k-coloring graph of a base graph G has vertex set consisting of the proper k-colorings of G and edge set consisting of the pairs of k-colorings that differ on a single vertex. A base graph whose k-coloring graph is connected is said to be k-mixing; it is possible to transition between any two k-colorings in a k-mixing graph via a sequence of single vertex recolorings, where each intermediate step is also a proper k-coloring. A natural extension of connectedness is biconnectedness. If a base graph has a coloring graph that is not biconnected, then there exists a proper k-coloring that would disconnect the coloring graph if removed. We call such a coloring a k-cut coloring. We prove that no base graph that is 3-mixing can have a 3-cut coloring, but for any k≥4 there exists a base graph that is k-mixing and has a k-cut coloring. [ABSTRACT FROM AUTHOR]

Given d≥2 and two rooted d-ary trees D and T such that D has k leaves, the density γ(D,T) of D in T is the proportion of all k-element subsets of leaves of T that induce a tree isomorphic to D, after contracting all vertices of outdegree 1. In a recent work, it was proved that the limit inferior of this density as the size of T grows to infinity is always zero unless D is the k-leaf binary caterpillar Fk2 (the binary tree with the property that a path remains upon removal of all the k leaves). Our main theorem in this paper is an exact formula (involving both d and k) for the limit inferior of γ(Fk2,T) as the size of T tends to infinity. [ABSTRACT FROM AUTHOR]

In this paper we introduce the 3-way intersection problem for G-designs, and we consider this problem for kite systems. Let bv=v(v-1)/8 and I3(v)={0,1,…,bv}\{bv-1}. Let J3(v)={s: there exist three kite systems of order v intersecting in s blocks}. We show that for any positive integer v≡0,1(mod8) and v≥8, J3(v)=I3(v). [ABSTRACT FROM AUTHOR]

An antimagic labelling of a graph G with m edges is a bijection f:E(G)→{1,…,m} such that for any two distinct vertices u, v we have ∑e∈E(v)f(e)≠∑e∈E(u)f(e), where E(v) denotes the set of edges incident v. The well-known Antimagic Labelling Conjecture formulated in 1994 by Hartsfield and Ringel states that any connected graph different from K2 admits an antimagic labelling. A weaker local version which we call the Local Antimagic Labelling Conjecture says that if G is a graph distinct from K2, then there exists a bijection f:E(G)→{1,…,|E(G)|} such that for any two neighbours u, v we have ∑e∈E(v)f(e)≠∑e∈E(u)f(e). This paper proves the following more general list version of the local antimagic labelling conjecture: Let G be a connected graph with m edges which is not a star. For any list L of m distinct real numbers, there is a bijection f:E(G)→L such that for any pair of neighbours u, v we have that ∑e∈E(v)f(e)≠∑e∈E(u)f(e). [ABSTRACT FROM AUTHOR]

In this paper, we introduce and study a new coloring problem of a graph called the dominated coloring. A dominated coloring of a graph $$G$$ is a proper vertex coloring of $$G$$ such that each color class is dominated by at least one vertex of $$G$$ . The minimum number of colors among all dominated colorings is called the dominated chromatic number, denoted by $$\chi _{dom}(G)$$ . In this paper, we establish the close relationship between the dominated chromatic number $$\chi _{dom}(G)$$ and the total domination number $$\gamma _t(G)$$ ; and the equivalence for triangle-free graphs. We study the complexity of the problem by proving its NP-completeness for arbitrary graphs having $$\chi _{dom}(G) \ge 4$$ and by giving a polynomial time algorithm for recognizing graphs having $$\chi _{dom}(G) \le 3$$ . We also give some bounds for planar and star-free graphs and exact values for split graphs. [ABSTRACT FROM AUTHOR]

A total coloring of a graph is an assignment of colors to all the elements of the graph in such a way that no two adjacent or incident elements receive the same color. In this paper, we prove Behzad-Vizing conjecture for product graphs. In particular, we obtain the tight bound for certain classes of graphs. [ABSTRACT FROM AUTHOR]

A Halin graph is constructed from a plane embedding of a tree with no vertices of degree 2 by adding a cycle through its leaves in the natural order determined by the embedding. Halin graphs satisfy interesting properties. However, to our knowledge, there are no results giving a positive answer for 'spanning Halin subgraph problem' (i.e., which graph has a Halin graph as a spanning subgraph) except for a conjecture by Lovász and Plummer which states that every 4-connected plane triangulation contains a spanning Halin subgraph. In this paper, we investigate the characterization of forbidden pairs guaranteeing the existence of a spanning Halin subgraph. In particular, we show that the set of such pairs is a very small class. Also, we show that $$\{ K_{1,3}, P_5 \}$$ belongs to the set, but neither $$\{ K_{1,4}, P_5 \}$$ nor $$\{ K_{1,3}, P_6 \}$$ belongs to the set. [ABSTRACT FROM AUTHOR]

Zhu, Li and Deng introduced in 1989 the definition of implicit degree of a vertex v in a graph G, denoted by id( v), by using the degrees of the vertices in its neighborhood and the second neighborhood. And they obtained sufficient conditions with implicit degrees for a graph to be hamiltonian. In this paper, we prove that if G is a 2-connected graph of order n ≥ 3 such that id( v) ≥ n/2 for each vertex v of G, then G is pancyclic unless G is bipartite, or else n = 4 r, r ≥ 2 and G is in a class of graphs F defined in the paper. [ABSTRACT FROM AUTHOR]

The concept of rainbow connection was introduced by Chartrand et al. [] in 2008. It is interesting and recently quite a lot papers have been published about it. In this survey we attempt to bring together most of the results and papers that dealt with it. We begin with an introduction, and then try to organize the work into five categories, including (strong) rainbow connection number, rainbow k-connectivity, k-rainbow index, rainbow vertex-connection number, algorithms and computational complexity. This survey also contains some conjectures, open problems and questions. [ABSTRACT FROM AUTHOR]

A graph G is called H-equicoverable if every minimal H-covering in G is also a minimum H-covering in G. All $$P_{3}$$ -equicoverable graphs were characterized in Zhang (Discret Appl Math 156:647-661, 2008). In 2011, connected $$M_2$$ -equicoverable graphs that contains cycles were characterized [see Zhang and Jiang (J Tianjin Univ:44:466-470, 2011) and Zhang and Zhang (Ars Comb 101:45-63, 2011)]. In this paper, we give the characterization of all disconnected $$M_{2}$$ -equicoverable graphs and all $$M_{2}$$ -equicoverable trees. So all $$M_2$$ -equicoverable graphs are characterized now. [ABSTRACT FROM AUTHOR]

In this paper we work to classify which of the ( n, k)-star graphs, denoted by $$S_{n,k}$$ , are Cayley graphs. Although the complete classification is left open, we derive infinite and non-trivial classes of both Cayley and non-Cayley graphs. We give a complete classification of the case when $$k=2$$ , showing that $$S_{n,2}$$ is Cayley if and only if n is a prime power. We also give a sufficient condition for $$S_{n,3}$$ to be Cayley and study other structural properties, such as demonstrating that $$S_{n,k}$$ always has a uniform shortest path routing. [ABSTRACT FROM AUTHOR]

A dominator coloring of a graph G is a proper coloring of G with the additional property that every vertex dominates an entire color class. The dominator chromatic number $$\chi _d(G)$$ of G is the minimum number of colors among all dominator colorings of G. In this paper, we determine the dominator chromatic numbers of Cartesian product graphs $$P_2 \square P_n$$ and $$P_2 \square C_n$$ . [ABSTRACT FROM AUTHOR]

Jaeger et al. conjectured that every 5-edge-connected graph is $$Z_3$$ -connected, which is equivalent to that every 5-edge-connected claw-free graph is $$Z_3$$ -connected by Lai et al. (Inf Process Lett 111:1085-1088, 2011), and Ma and Li (Discret Math 336:57-68, 2014). Let G be a claw-free graph on at least 3 vertices such that there are at least two common neighbors of every pair of 2-distant vertices. In this paper, we prove that G is not $$Z_3$$ -connected if and only if G is one of seven specified graphs, or three families of well characterized graphs. As a corollary, G does not admit a nowhere-zero 3-flow if and only if G is one of three specified graphs or a family of well characterized graphs. [ABSTRACT FROM AUTHOR]

Duval, in (J Comb Theory Ser 47:71-100, 1988), introduced the concept of directed strongly regular graphs. In this paper we construct rich families of directed strongly regular graphs with new parameters. Our constructions yielding new parameters are based on extending known explicit constructions to cover more parameter sets. [ABSTRACT FROM AUTHOR]

Back in 1922, Franklin proved that every 3-polytope $$P_5$$ with minimum degree 5 has a 5-vertex adjacent to two vertices of degree at most 6, which is tight. This result has been extended and refined in several directions. In particular, Jendrol' and Madaras (Discuss Math Graph Theory 16:207-217, 1996) ensured a 4-path with the degree sum at most 23. A path $$v_1\ldots v_k$$ is a $$(d_1,\ldots d_k)$$ -path if $$d(v_i)\le d_i$$ whenever $$1\le i\le k$$ . Recently, Borodin and Ivanova proved that every $$P_5$$ has a (6, 5, 6, 6)-path or (5, 5, 5, 7)-path, and Ivanova proved the existence of a (5, 6, 6, 6)-path or (5, 5, 5, 7)-path, where both descriptions are tight. The purpose of our paper is to give all tight descriptions of 4-paths in $$P_5$$ s. [ABSTRACT FROM AUTHOR]

The subdivision graph S( Σ) of a connected graph Σ is constructed by adding a vertex in the middle of each edge. In a previous paper written with Cheryl E. Praeger, we characterised the graphs Σ such that S( Σ) is locally ( G, s)-distance transitive for s ≤ 2 diam( Σ) − 1 and some G ≤ Aut( Σ). In this paper, we solve the remaining cases by classifying all the graphs Σ such that S( Σ) is locally ( G, s)-distance transitive for some s ≥ 2 diam( Σ) and some G ≤ Aut( Σ). As a corollary, we get a classification of all the graphs whose subdivision graph is locally distance transitive. [ABSTRACT FROM AUTHOR]

Hua et al. (Discrete Math 311, 2259-2267, 2011) and Yang et al. (Discrete Math. 339, 522-532, 2016) classify arc-transitive pentavalent graphs of order 2 pq and of order 2 pqr (with p, q, r distinct odd primes), respectively. In this paper, we extend their results by giving a classification of arc-transitive pentavalent graphs of any square-free order. [ABSTRACT FROM AUTHOR]

A graph is computable if there is an algorithm which decides whether given vertices are adjacent. Having a procedure for deciding the edge set might not help compute other properties or features of the graph, however. The goal of this paper is to investigate the extent to which features related to the planarity of a graph might or might not be computable. We propose three definitions for what it might mean for a computable graph to be computably planar and for each build a computable planar graph which fails to be computably planar. We also consider these definitions in the context of highly computable graphs, those for which there is an algorithm which computes the degree of a given vertex. [ABSTRACT FROM AUTHOR]

A clique-transversal of a graph G is a subset of vertices that meets all the cliques of G. A clique-independent set is a collection of pairwise vertex-disjoint cliques. A graph G is clique-perfect if the sizes of a minimum clique-transversal and a maximum clique-independent set are equal for every induced subgraph of G. An open problem concerning clique-perfect graphs is to find all minimal forbidden induced subgraphs of clique-perfect graphs. In this paper we characterize the clique-perfectness of claw-free planar graphs by forbidden induced subgraphs. Furthermore, we also characterize the clique-perfectness of claw-free graphs with degree at most 4 and graphs with degree at most 3. As an immediate corollary, we show that claw-free cubic graphs are clique-perfect. [ABSTRACT FROM AUTHOR]

Two resolutions of the same 3-design are said to be orthogonal when each parallel class of one resolution has at most one block in common with each parallel class of the other resolution. If an H design has two orthogonal resolutions, then the H design is called a doubly resolvable H design. In this paper, we construct two infinite classes of doubly resolvable H( n, g, 4, 3)s for $$n=6$$ or 8 and use a quadrupling construction to obtain more infinite classes of doubly resolvable H designs. [ABSTRACT FROM AUTHOR]

In this paper we give a strategy for constructing half-arc-transitive graphs of valency four with prescribed vertex stabilizers. This strategy is applied to answer a 2001 outstanding question of Roman Nedela and Dragan Marušič. [ABSTRACT FROM AUTHOR]

A graph is vertex-transitive if its automorphism group acts transitively on vertices of the graph. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, a complete classification is given of tetravalent vertex-transitive non-Cayley graphs of order $$2p^2$$ for any prime p. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

A graph $$G=(V,E)$$ is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if $$(x,y)\in E$$ . A triangular grid graph is a subgraph of a tiling of the plane with equilateral triangles defined by a finite number of triangles, called cells. A face subdivision of a triangular grid graph is replacing some of its cells by plane copies of the complete graph $$K_4$$ . Inspired by a recent elegant result of Akrobotu et al., who classified word-representable triangulations of grid graphs related to convex polyominoes, we characterize word-representable face subdivisions of triangular grid graphs. A key role in the characterization is played by smart orientations introduced by us in this paper. As a corollary to our main result, we obtain that any face subdivision of boundary triangles in the Sierpiński gasket graph is word-representable. [ABSTRACT FROM AUTHOR]

Aztec dragons are lattice regions first introduced by James Propp, which have the number of tilings given by a power of 2. This family of regions has been investigated further by a number of authors. In this paper, we consider a generalization of the Aztec dragons to two new families of 6-sided regions. By using Kuo's graphical condensation method, we prove that the tilings of the new regions are always enumerated by powers of 2 and 3. [ABSTRACT FROM AUTHOR]

In this paper, we continue the study of total restrained domination in graphs. A set S of vertices in a graph G = ( V, E) is a total restrained dominating set of G if every vertex of G is adjacent to some vertex in S and every vertex of $${V {\setminus} S}$$ is adjacent to a vertex in $${V {\setminus} S}$$ . The minimum cardinality of a total restrained dominating set of G is the total restrained domination number γ( G) of G. Jiang et al. (Graphs Combin 25:341-350, ) showed that if G is a connected cubic graph of order n, then γ( G) ≤ 13 n/19. In this paper we improve this upper bound to γ( G) ≤ ( n + 4)/2. We provide two infinite families of connected cubic graphs G with γ( G) = n/2, showing that our new improved bound is essentially best possible. [ABSTRACT FROM AUTHOR]

The Hadwiger number η( G) of a graph G is the largest integer n for which the complete graph K n on n vertices is a minor of G. Hadwiger conjectured that for every graph G, η( G) ≥ χ( G), where χ( G) is the chromatic number of G. In this paper, we study the Hadwiger number of the Cartesian product $$G \square H$$ of graphs. As the main result of this paper, we prove that $$\eta (G_1 \square G_2) \ge h\sqrt{l}\left (1 - o(1) \right )$$ for any two graphs G 1 and G 2 with η( G 1) = h and η( G 2) = l. We show that the above lower bound is asymptotically best possible when h ≥ l. This asymptotically settles a question of Z. Miller (1978). As consequences of our main result, we show the following: [ABSTRACT FROM AUTHOR]

In this paper we develop two methods for completing partial latin squares and prove the following. Let $$A$$ be a partial latin square of order $$nr$$ in which all non-empty cells occur in at most $$n-1$$ $$r\times r$$ squares. If $$t_1,\ldots , t_m$$ are positive integers for which $$n\geqslant t_1^2+t_2^2+\cdots +t_m^2+1$$ and if $$A$$ is the union of $$m$$ subsquares each with order $$rt_i$$ , then $$A$$ can be completed. We additionally show that if $$n\geqslant r+1$$ and $$A$$ is the union of $$n$$ identical $$r\times r$$ squares with disjoint rows and columns, then $$A$$ can be completed. For smaller values of $$n$$ we show that a completion does not always exist. [ABSTRACT FROM AUTHOR]

In this paper we investigate the structures of short cycles in a weighted graph. By Thomassen's $$3$$ -path-condition theory (Thomassen in J Comb Theory Ser 48:155-177, ), it is easy to find a shortest cycle in a collection of cycles beyond a subspace of the cycle space of a graph. What is more difficult for one to do is to find a shortest cycle within a subspace of the cycle space in polynomial time. By using the Dijkstra's algorithm (Dijkstra in Numer Math 1:55-61, ) we find a collection $$\mathcal {C}$$ of cycles containing many types of short cycles within a given subspace of the cycle space of a graph and this implies a polynomial time algorithm (called extended fundamental cycle algorithm) to locate all the possible shortest cycles in a weighted graph. In the case of unweighted graphs, the algorithm may also find every shortest even cycle in a graph, this greatly improved a result of Grötschel and Pulleyblank (Oper Res Lett 1:23-27, ), Monien (Computing 31:355-369, ), Yuster and Zwick (SIAM J Discrete Math 10:209-222, ). In fact, our algorithm shows that there are at most $$O(n^4)$$ many such short cycles in an unweighted graph of order $$n$$ . Further more, our fundamental cycle method may find a minimum cycle base (or simply MCB as some scholars named) in the cycle space of a graph. Since the structure of MCB's is unique (Ren and Deng in Discrete Math 307:2654-2660, ), this shows that, in the sense, cycles in a MCB are nearly-fundamental (i.e., each element in a MCB is a sum of at most two fundamental cycles). This provides a new way to study MCB. [ABSTRACT FROM AUTHOR]

Let $$G$$ and $$G'$$ be two simple connected nontrivial graphs. Denote by $$G\Box G^{'}$$ and $$G\rho G^{'}$$ the Cartesian product and the Wreath product of $$G$$ and $$G^{'}$$ , respectively. In this paper, we will show two results: (1) if $$G^{'}$$ is a triangularly connected simple graph with $$|V(G^{'})|\ge 3$$ which is neither $$K_{2,t}^{+}$$ nor one specific graph, then $$G\Box G^{'}$$ is $$Z_{3}$$ -connected; (2) if $$G^{'}$$ is a vertex-transitive graph, then $$G\rho G^{'}$$ is $$Z_{3}$$ -connected. [ABSTRACT FROM AUTHOR]

In this paper we obtain an intermediate value theorem for the decycling numbers of Toeplitz graphs: if $$n \ge 3$$ , and $$0 \le r \le n - 2$$ , then there exists a Toeplitz graph of order $$n$$ with decycling number $$r$$ . We also prove that the decycling numbers of connected Cayley graphs of order $$n$$ satisfy the intermediate value property if and only if $$n = 4$$ or $$6$$ . [ABSTRACT FROM AUTHOR]

Let $$D=(V(D), A(D))$$ be a digraph, $$DP(D)$$ be the set of directed paths of $$D$$ and let $$\varPi $$ be a subset of $$DP(D)$$ . A subset $$S\subseteq V(D)$$ will be called $$\varPi $$ -independent if for any pair $$\{x, y\} \subseteq S$$ , there is no $$xy$$ -path nor $$yx$$ -path in $$\varPi $$ ; and will be called $$\varPi $$ -absorbing if for every $$x\in V(D)\setminus S$$ there is $$y\in S$$ such that there is an $$xy$$ -path in $$\varPi $$ . A set $$S\subseteq V(D)$$ will be called a $$\varPi $$ -kernel if $$S$$ is $$\varPi $$ -independent and $$\varPi $$ -absorbing. This concept generalize several 'kernel notions' like kernel or kernel by monochromatic paths, among others. In this paper we present some sufficient conditions for the existence of $$\varPi $$ -kernels. [ABSTRACT FROM AUTHOR]

A frame matroid $$M$$ is graphic if there is a graph $$G$$ with cycle matroid isomorphic to $$M$$ . In general, if there is one such graph, there will be many. Zaslavsky has shown that frame matroids are precisely those having a representation as a biased graph; this class includes graphic matroids, bicircular matroids, and Dowling geometries. Whitney characterized which graphs have isomorphic cycle matroids, and Matthews characterized which graphs have isomorphic graphic bicircular matroids. In this paper, we give a characterization of which biased graphs give rise to isomorphic graphic frame matroids. [ABSTRACT FROM AUTHOR]

It has long been conjectured that the total chromatic number $$ \chi ^{\prime \prime }(K)$$ of the complete $$p$$ -partite graph $$K = K(r_1, \dots , r_p)$$ is $$\Delta (K) + 1$$ if and only if both $$K \ne K_{r,r}$$ and $$|V(K)| \equiv $$ 0 (mod 2) implies that $$\Sigma _{v \in V(K)}(\Delta (K) - d_K(v))$$ is at least the number of parts of odd size. It is known that $$\chi ^{\prime \prime }(K) \le \Delta (K) + 2$$ . In this paper, a new approach is introduced to attack the conjecture that makes use of amalgamations of graphs. The power of this approach is demonstrated by settling the conjecture for all complete 5-partite graphs. [ABSTRACT FROM AUTHOR]

For two given graphs $$G_1$$ and $$G_2$$ , the planar Ramsey number $$PR(G_1,G_2)$$ is the smallest integer $$N$$ such that for any planar graph $$G$$ of order $$N$$ , either $$G$$ contains $$G_1$$ or the complement of $$G$$ contains $$G_2$$ . Let $$K_m$$ denote a complete graph of order $$m$$ and $$W_n$$ a wheel of order $$n+1$$ . In this paper, we determine all planar Ramsey numbers $$PR(K_m,W_n)$$ . [ABSTRACT FROM AUTHOR]

In this paper, we characterize connected $$\{K_{1,3},N(2,1,0)\}$$ -free but not $$N(1,1,1)$$ -free graphs. By combining our result and a theorem showed by Duffus et al. (every $$2$$ -connected $$\{K_{1,3},N(1,1,1)\}$$ -free graph is Hamiltonian), we give an alternative proof of Bedrossian's theorem (every $$2$$ -connected $$\{K_{1,3},N(2,1,0)\}$$ -free graph is Hamiltonian). [ABSTRACT FROM AUTHOR]

For a graph $$G$$ , let $$\delta _F(G)=\min \{\max \{d(u), d(v)\} | \text{ for } \text{ any }~u, v\in V(G)\, \text{ with } \text{ distance }~2\}$$ . A graph is supereulerian if it has a spanning Eulerian subgraph. Let $$p>0$$ , $$g>2$$ and $$\epsilon $$ be given nonnegative numbers. Let $$\mathcal{Q}$$ be the family of non-supereulerian graphs with order at most $$5(p-2)$$ . In this paper, we prove that for a 3-edge-connected graph $$G$$ of order $$n$$ , if $$G$$ satisfies a Fan-type condition $$\delta _F(G)\ge \frac{n}{(g-2)p}-\epsilon $$ and $$n$$ is sufficiently large, then $$G$$ is supereulerian if and only if $$G$$ is not contractible to a graph in $$\mathcal{Q}$$ . Results on best possible values of $$p$$ and $$\epsilon $$ for such graphs to either be supereulerian or be contractible to the Petersen graph are given. [ABSTRACT FROM AUTHOR]

Indicated coloring is a graph coloring game in which there are two players collectively coloring the vertices of a graph in the following way. In each round the first player (Ann) selects a vertex, and then the second player (Ben) colors it properly, using a fixed set of colors. The goal of Ann is to achieve a proper coloring of the whole graph $$G$$ , while Ben is trying to prevent the realization of this project. The smallest number of colors necessary for Ann to win the game on a graph $$G$$ (regardless of Ben's strategy) is called the indicated chromatic number of $$G$$ , and is denoted by $$\chi _i(G)$$ . In this paper, we have shown that cographs, chordal graphs, complement of bipartite graphs, $$\{P_5,K_3\}$$ -free graphs and $$\{P_5, \mathrm{paw}\}$$ -free graphs are $$k$$ -indicated colorable for all $$k\ge \chi _i(G)$$ . This provides a partial answer to a question raised in Grzesik (Discret Math 312:3467-3472, ). Also we have discussed the Brooks' type result for indicated coloring. [ABSTRACT FROM AUTHOR]

In this paper, we give necessary and sufficient conditions for the existence of large sets of almost Hamilton cycle decompositions of $$\lambda K_{m,n}$$ . We also give necessary and sufficient conditions for the existence of large sets of almost Hamilton path decompositions of $$\lambda K_{n,n}$$ . [ABSTRACT FROM AUTHOR]

If a graph $$G$$ has three even subgraphs $$C_1$$ , $$C_2$$ and $$C_3$$ such that every edge of $$G$$ lies in exactly two members of $$\{C_1, C_2, C_3\}$$ , then we say that $$G$$ has a 3-cycle-2-cover. Let $$S_3$$ denote the family of graphs that admit a 3-cycle-2-cover, and let $$\mathcal {S}(h,k) = \{G:$$ $$G$$ is at most $$h$$ edges short of being $$k$$ -edge-connected $$\}$$ . Catlin (J Gr Theory 13:465-483, ) introduced a reduction method such that a graph $$G \in S_3$$ if its reduction is in $$S_3$$ ; and proved that a graph in the graph family $$\mathcal {S}(5,4)$$ is either in $$S_3$$ or its reduction is in a forbidden collection consisting of only one graph. In this paper, we introduce a weak reduction for $$S_3$$ such that a graph $$G \in S_3$$ if its weak reduction is in $$S_3$$ , and identify several graph families, including $$\mathcal {S}(h,4)$$ for an integer $$h \ge 0$$ , with the property that any graph in these families is either in $$S_3$$ , or its weak reduction falls into a finite collection of forbidden graphs. [ABSTRACT FROM AUTHOR]

A graph $$G$$ is $$F$$ -saturated if it has no $$F$$ as a subgraph, but does contain $$F$$ after the addition of any new edge. The saturation number, $$sat(n,F)$$ , is the minimum number of edges of a graph in the set of all $$F$$ -saturated graphs with order $$n$$ . In this paper, we determine the saturation number $$sat(n,P_5\cup tP_2)$$ for $$n\ge 3t+8$$ and characterize the extremal graphs for $$n>(18t+76)/5$$ . [ABSTRACT FROM AUTHOR]

The square of a graph is obtained by adding additional edges joining all pair of vertices of distance two in the original graph. Particularly, if $$C$$ is a hamiltonian cycle of a graph $$G$$ , then the square of $$C$$ is called a hamiltonian square of $$G$$ . In this paper, we characterize all possible forbidden pairs, which implies the containment of a hamiltonian square, in a 4-connected graph. The connectivity condition is necessary as, except $$K_3$$ and $$K_4$$ , the square of a cycle is always 4-connected. [ABSTRACT FROM AUTHOR]

In 1986, Terwilliger showed that there is a strong relation between the eigenvalues of a distance-regular graph and the eigenvalues of a local graph. In particular, he showed that the eigenvalues of a local graph are bounded in terms of the eigenvalues of a distance-regular graph, and he also showed that if an eigenvalue $$\theta $$ of the distance-regular graph has multiplicity m less than its valency k, then $$-1- \frac{b_1}{\theta +1}$$ is an eigenvalue for any local graph with multiplicity at least $$k-m$$ . In this paper, we are going to generalize the results of Terwilliger to a broader class of subgraphs. Instead of local graphs, we consider induced subgraphs of distance-regular graphs (and more generally t-walk-regular graphs with t a positive integer) which satisfies certain regularity conditions. Then we apply the results to obtain bounds on eigenvalues of t-walk-regular graphs if the girth equals 3, 4, 5, 6 or 8. In particular, we will show that the second largest eigenvalue of a distance-regular graph with girth 6 and valency k is at most $$k-1$$ , and we will show that the only such graphs having $$k-1$$ as its second largest eigenvalue are the doubled Odd graphs. [ABSTRACT FROM AUTHOR]

A graph $$G=(V,E)$$ is called factor-critical if $$G\ne \emptyset $$ and $$G-v$$ has a perfect matching for every vertex $$v\in V(G)$$ . A factor-critical graph $$G$$ is tight (anti-tight, respectively) if for any $$v\in V(G)$$ , any perfect matching $$M$$ in $$G-v$$ , and any $$e\in M$$ , $$|N(v)\cap V(e)|\ne 1$$ ( $$|N(v)\cap V(e)|\ne 2$$ , respectively), where $$N(v)$$ denotes the neighborhood of $$v$$ and $$V(e)$$ denotes the set of vertices incident with $$e$$ . A graph $$G$$ is minimally anti-tight if $$G$$ is anti-tight but $$G-e$$ is not anti-tight for every $$e\in E(G)$$ . In this paper, we prove that a connected graph is tight iff every block of the graph is an odd clique, and that every minimally anti-tight graph is triangle-free. [ABSTRACT FROM AUTHOR]

The domination polynomial of a graph is the polynomial whose coefficients count the number of dominating sets of each cardinality. A recent question asks which graphs are uniquely determined (up to isomorphism) by their domination polynomial. In this paper, we completely describe the complete $$r$$ -partite graphs which are; in the bipartite case, this settles in the affirmative a conjecture of Aalipour et al. (Ars Comb, ). [ABSTRACT FROM AUTHOR]