# Graphs and Combinatorics

Graphs and Combinatorics > 2017 > 33 > 1 > 123-140

*G*be a claw-free graph on at least 3 vertices such that there are at least two common neighbors...

Graphs and Combinatorics > 2017 > 33 > 1 > 233-243

*F*satisfying $$F \rightarrow (G,H)$$ F → ( G , H ) and for every $$e \in E(F),$$ e ∈ E ( F ) , $$(F-e) \nrightarrow (G,H).$$ ( F - e ) ↛ ( G , H ) . In this paper, we derive the necessary and sufficient conditions for graphs belonging to $$\mathcal {R}(mK_2,H)$$ R ( m K 2 , H ) ...

Graphs and Combinatorics > 2017 > 33 > 1 > 43-51

*D*of order 2

*a*is hamiltonian, provided $$a\ge 3$$ a ≥ 3 and $$d(x)+d(y)\ge 3a$$ d ( x ) + d ( y ) ≥ 3 a for every pair of vertices

*x*,

*y*with a common in-neighbour or a common out-neighbour in

*D*.

Graphs and Combinatorics > 2017 > 33 > 1 > 181-201

*G*with $$|G| \ge 3k$$ | G | ≥ 3 k and minimum degree at least 2

*k*contains

*k*vertex-disjoint cycles. In 2008, Finkel proved that for all $$k \ge 1$$ k ≥ 1 , any graph

*G*with $$|G| \ge 4k$$ | G | ≥ 4 k and minimum degree at least 3

*k*contains

*k*vertex-disjoint...

Graphs and Combinatorics > 2017 > 33 > 1 > 203-219

Graphs and Combinatorics > 2017 > 33 > 1 > 1-41

*t*-designs and combinatorial

*t*-designs, as well as

*t*-designs in Q-polynomial association schemes. (ii) Euclidean

*t*-designs as a two-step generalization of spherical

*t*-designs. (iii) Relative

*t*-designs as a two-step generalization...

Graphs and Combinatorics > 2017 > 33 > 1 > 149-156

*J*(

*N*,

*D*). This observation suggests that the main theorems of Levstein and Maldonado (Discrete Math 307:1621–1635, 2007) and Lv et al. (Discrete Math 328:54–62, 2014), i.e, Theorem...

Graphs and Combinatorics > 2017 > 33 > 1 > 157-169

*G*is called a pseudo-core if every endomorphism of

*G*is either an automorphism or a colouring. An interesting problem in graph theory is to distinguish whether a graph is a core. The twisted Grassmann graphs, constructed by van Dam and Koolen in (Invent Math 162:189–193, 2005), are the first known family of non-vertex-transitive distance-regular graphs with unbounded diameter. In this paper,...

Graphs and Combinatorics > 2017 > 33 > 1 > 103-122

*t*-stack sortable permutations of length

*n*and

*t*-stack sortable permutations of length

*n*with exactly

*k*descents. From these bounds, we are able to significantly...

Graphs and Combinatorics > 2017 > 33 > 1 > 171-179

Graphs and Combinatorics > 2017 > 33 > 1 > 53-62

Graphs and Combinatorics > 2017 > 33 > 1 > 85-102

*n*,

*k*)-star graphs, denoted by $$S_{n,k}$$ 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$$ k = 2 , showing that $$S_{n,2}$$ S n , 2 is Cayley if and...

Graphs and Combinatorics > 2017 > 33 > 1 > 141-148

*r*such that for every graph

*G*on

*r*vertices, either

*G*contains a $$G_1$$ G 1 or $$\overline{G}$$ G ¯ contains a $$G_2$$ G 2 . A complete bipartite graph $$K_{1,n}$$ K 1 , n is called a star. The...

Graphs and Combinatorics > 2017 > 33 > 1 > 73-83

*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)$$ χ 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$$ ...

Graphs and Combinatorics > 2017 > 33 > 1 > 245-256

*G*is called

*H*-equicoverable if every minimal

*H*-covering in

*G*is also a minimum

*H*-covering in

*G*. All $$P_{3}$$ P 3 -equicoverable graphs were characterized in Zhang (Discret Appl Math 156:647–661, 2008). In 2011, connected $$M_2$$ 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...

Graphs and Combinatorics > 2017 > 33 > 1 > 221-231

*t*-bar visibility representation of a graph

*G*assigns each vertex a union of at most

*t*horizontal segments (“bars”) in the plane so that vertices

*u*and

*v*are adjacent if and only if some bar assigned to

*u*and some bar assigned to

*v*are joined by an unobstructed vertical line of sight having positive width. For an oriented graph

*G*, having an edge

*uv*requires visibility from a bar for

*u*upward to a...

Graphs and Combinatorics > 2017 > 33 > 1 > 63-71

Graphs and Combinatorics > 2017 > 33 > 2 > 387-401

Graphs and Combinatorics > 2017 > 33 > 2 > 287-305

*m*and diameter

*d*, the labeling produces vertex labels no greater than $$\frac{3}{2}m-\frac{1}{2}d$$...

Graphs and Combinatorics > 2017 > 33 > 2 > 257-274

*F*and

*H*with Ramsey number $$R(F, H) = n$$ R ( F , H ) = n and an integer

*k*with $$2 \le k \le n$$ 2 ≤ k ≤ n , the

*k*-Ramsey number of

*F*and

*H*is the minimum order of a balanced complete

*k*-partite graph

*G*for which every red-blue coloring of

*G*results in a subgraph of

*G*isomorphic to

*F*all of whose edges are colored red or a subgraph isomorphic to

*H*all of...