Search

We give a very short and simple proof of Zykov’s generalization of Turán’s theorem, which implies that the number of maximum independent sets of a graph of order n and independence number α with αn, and we also characterize the extremal graphs. Finally, we show that the number of maximum independent sets of a subcubic tree of order n and independence number α is at most 1+522n-3α+1, and we provide more precise results for extremal values of α. [ABSTRACT FROM AUTHOR]

An odd (resp. even) subgraph in a multigraph is its subgraph in which every vertex has odd (resp. even) degree. We say that a multigraph can be decomposed into two odd subgraphs if its edge set can be partitioned into two sets so that both form odd subgraphs. In this paper we give a necessary and sufficient condition for thedecomposability of a multigraph into two odd subgraphs. We also present a polynomial time algorithm for finding such a decomposition or showing its non-existence. We also deal with the case of the decomposability into an even subgraph and an odd subgraph. [ABSTRACT FROM AUTHOR]

The neighborhood complex of a graph is the family of subsets of open neighborhoods of its vertices. The neighborhood polynomial is the ordinary generating function for the number of sets of the neighborhood complex with respect to their cardinality. This paper provides a new representation of the neighborhood polynomial as a sum over complete bipartite subgraphs of a graph. Using the close relation between the domination polynomial and the neighborhood polynomial of a graph, we can also give a new presentation of the domination polynomial. Finally we show that finding the number of certain double cliques of a graph is sufficient to determine the number of dominating sets of a graph. [ABSTRACT FROM AUTHOR]

Given graphs G and H, G is H-saturated if G does not contain a copy of H but the addition of any edge e∉E(G) creates at least one copy of H within G. The edge spectrum of H is the set of all possible sizes of an H-saturated graph on n vertices. Let K4- be the graph obtained from K4 by deleting an edge. In this note, we show that (a) if G is a K4--saturated graph with |V(G)|=n and |E(G)|>⌊n-12⌋⌈n-12⌉+2, then G must be a bipartite graph; (b) there exists a K4--saturated non-bipartite graph on n≥8 vertices with size being in the interval 3n-11,n-12n-12+2. Together with a result of Fuller and Gould (Graphs Combin 34:85-95, 2018), we determine the edge spectrum of K4- completely, and a conjecture proposed by Fuller and Gould in the same paper also has been resolved. [ABSTRACT FROM AUTHOR]

Gallai-Ramsey numbers often consider edge-colorings of complete graphs in which there are no rainbow triangles. Within such colored complete graphs, the goal is to look for specified monochromatic subgraphs. We consider an “off diagonal” case of this concept by looking for either a monochromatic K3 in one of some set of colors or a monochromatic C4 in one of some other set of colors. [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]

The chromatic edge stability number esχ(G) of a graph G is the minimum number of edges whose removal results in a graph H⊆G with chromatic number χ(H)=χ(G)-1. The chromatic bondage number ρ(G) of G is the minimum number of edges between any two color classes in a χ(G)-coloring of G, where the minimum is taken over all χ(G)-colorings of G. In this paper, we characterize graphs for which these two parameters coincide. Moreover, we give general bounds and we determine these parameters for several classes of graphs. [ABSTRACT FROM AUTHOR]

We derive a simple bijection between geometric plane perfect matchings on 2n points in convex position and triangulations on n+2 points in convex position. We then extend this bijection to monochromatic plane perfect matchings on periodically k-colored vertices and (k+2)-gonal tilings of convex point sets. These structures are related to a generalization of Temperley-Lieb algebras and our bijections provide explicit one-to-one relations between matchings and tilings. Moreover, for a given element of one class, the corresponding element of the other class can be computed in linear time. [ABSTRACT FROM AUTHOR]

In 2000, Enomoto and Ota conjectured that if a graph G satisfies σ2(G)≥|G|+k-1, then for any set of k vertices v1,…,vk and for any positive integers n1,…,nk with ∑ni=|G|, there exists a partition of V(G) into k paths P1,…,Pk such that vi is an end of Pi and |Pi|=ni for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. [ABSTRACT FROM AUTHOR]

Let G be a graph embedded in a surface of nonnegative characteristic with maximum degree Δ. The entire chromatic number χvef of G is the least number of colors such that any two adjacent or incident elements in V(G)∪E(G)∪F(G) have different colors. In this paper, we prove that χvef(G)≤Δ+4 if Δ≥6, and χvef(G)≤Δ+5 if Δ≤5. [ABSTRACT FROM AUTHOR]

An equitable coloring is a proper coloring of a graph such that the sizes of the color classes differ by at most one. A graph G is equitably k-colorable if there exists an equitable coloring of G which uses k colors, each one appearing on either ⌊|V(G)|/k⌋ or ⌈|V(G)|/k⌉ vertices of G. In 1994, Fu conjectured that for any simple graph G, the total graph of G, T(G), is equitably k-colorable whenever k≥max{χ(T(G)),Δ(G)+2} where χ(T(G)) is the chromatic number of the total graph of G and Δ(G) is the maximum degree of G. We investigate the list coloring analogue. List coloring requires each vertex v to be colored from a specified list L(v) of colors. A graph is k-choosable if it has a proper list coloring whenever vertices have lists of size k. A graph is equitably k-choosable if it has a proper list coloring whenever vertices have lists of size k, where each color is used on at most ⌈|V(G)|/k⌉ vertices. In the spirit of Fu’s conjecture, we conjecture that for any simple graph G, T(G) is equitably k-choosable whenever k≥max{χl(T(G)),Δ(G)+2} where χl(T(G)) is the list chromatic number of T(G). We prove this conjecture for all graphs satisfying Δ(G)≤2 while also studying the related question of the equitable choosability of powers of paths and cycles. [ABSTRACT FROM AUTHOR]

In this paper we consider one of the most extensively studied graph search parameters, namely the zero-forcing number of a graph. We relate the zero-forcing number to the brushing number, which as a graph parameter gained recent attention due to certain industrial applications where a network system needs to be cleaned efficiently. In particular, we prove that the zero-forcing number of the line graph is an upper bound for the brushing number by constructing a brush configuration based on a zero-forcing set for the line graph. Eroh, Kang and Yi conjectured that the zero-forcing number of a graph is no more than the zero-forcing number of its line graph, which we settle in the affirmative. Moreover we prove that the brushing number of a graph is no more than the brushing number of its line graph. All three bounds are shown to be tight. [ABSTRACT FROM AUTHOR]

Two graphs are adjacency cospectral (respectively, permanental cospectral) if they have the same adjacency spectrum (respectively, permanental spectrum). In this paper, we present a new method to construct new adjacency cospectral and permanental cospetral pairs of graphs from smaller ones. As an application, we obtain an infinite family of pairs of Cartesian product graphs which are adjacency cospectral and permanental cospetral. [ABSTRACT FROM AUTHOR]

Korpelainen, Lozin, and Razgon conjectured that a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by only finitely many minimal forbidden induced subgraphs is labelled well-quasi-ordered, a notion stronger than that of n-well-quasi-order introduced by Pouzet in the 1970s. We present a counterexample to this conjecture. In fact, we exhibit a hereditary property of graphs which is well-quasi-ordered by the induced subgraph order and defined by finitely many minimal forbidden induced subgraphs yet is not 2-well-quasi-ordered. This counterexample is based on the widdershins spiral, which has received some study in the area of permutation patterns. [ABSTRACT FROM AUTHOR]

An octad triple is a set of three octads, octads being the blocks of the S(5, 8, 24) Steiner system. In this paper we determine the orbits of M24, the largest Mathieu group, upon the set of octad triples. [ABSTRACT FROM AUTHOR]

A graph G of order n≥3 is pancyclic if G contains a cycle of each possible length from 3 to n, and vertex pancyclic (edge pancyclic) if every vertex (edge) is contained on a cycle of each possible length from 3 to n. A chord of a cycle is an edge between two nonadjacent vertices of the cycle, and chorded cycle is a cycle containing at least one chord. We define a graph G of order n≥4 to be chorded pancyclic if G contains a chorded cycle of each possible length from 4 to n. In this article, we consider extensions of the property of being chorded pancyclic to chorded vertex pancyclic and chorded edge pancyclic. [ABSTRACT FROM AUTHOR]

The fundamental group of the complement of a hyperplane arrangement in a complex vector space is an important topological invariant. The third rank of successive quotients in the lower central series of the fundamental group was called Falk invariant of the arrangement since Falk gave the first combinatorial formula and asked to give a combinatorial interpretation. In this article we prove that the Falk invariant of an arrangement associated with signed graph G without loops is double of the sum of k3, k4 and k3±, where kl is the number of subgraphs of G that are switching equivalent to the cliques with l vertices, k3± is that of subgraphs which have 3 vertices and each two vertices are connected by double edges with different signs. This formula modifies the one given by Schenck and Suciu, and answers partially Falk’s question in the case of signed graphic arrangements. [ABSTRACT FROM AUTHOR]

This note provides a new perspective, i.e., graph embeddings on the decycling number ∇(G) (Beineke and Vandell in J Graph Theory 25:59-77, 1997) of a graph G. For this point, it is shown that ∇(G)=γM(G)+ξ(G) for any cubic graph G and |S|=β(G)+m(S)k-1 for any decycling set S of a k-regular graph G, where γM(G), ξ(G), β(G) and m(S)=c(G-S)+|E(S)|-1 (c(G-S) is the number of components of G-S and |E(S)| is the number of edges in a subgraph G[S]) are, respectively, the maximum genus, the Betti deficiency (Xuong in J Combin Theory Ser B 26:217-225, 1979), the cycle rank (Harary in Graph theory, Academic Press, New York, 1967) and the margin number of G. Meanwhile, we further confirm that (1) a cubic graph G (G≠K4) has a vertex partition (V1,V2) such that V1 is an independent set and V2 induces a forest and (2) a k-regular graph G with ∇(G)=β(G)+m(S)k-1 (m(S)≤2) has a vertex partition (S,G-S) such that G[S] contains at most two edges and G-S induces a forest, where S is the smallest decycling set of G. Resorting to the above vertex partitions, we get the adjacent vertex distinguishing (AVD) total chromatic numbers of some families of graphs, and these results verify Zhang’s conjecture (Zhang in Sci China Ser A 48:289-299, 2005) that every graph with maximum degree Δ has an AVD-total (Δ+3)-coloring. [ABSTRACT FROM AUTHOR]

In this paper, we study (zero) forcing sets which induce connected subgraphs of a graph. The minimum cardinality of such a set is called the connected forcing number of the graph. We provide sharp upper and lower bounds on the connected forcing number in terms of the minimum degree, maximum degree, girth, and order of the graph. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is conflict-free connected if every two of its vertices are connected by a path, which contains a color 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 colors needed in order to make G conflict-free connected. For a graph G,  let C(G) be the subgraph of G induced by its set of cut-edges. In this paper, we first show that, if G is a connected non-complete graph G of order n≥9 with C(G) being a linear forest and with the minimum degree δ(G)≥max{3,n-45}, then cfc(G)=2. The bound on the minimum degree is best possible. Next, we prove that, if G is a connected non-complete graph of order n≥33 with C(G) being a linear forest and with d(x)+d(y)≥2n-95 for each pair of two nonadjacent vertices x, y of V(G), then cfc(G)=2. Both bounds, on the order n and the degree sum, are tight. Moreover, we prove several results concerning relations between degree conditions on G and the number of cut edges in G. [ABSTRACT FROM AUTHOR]

A graph is called H-free if it has no induced subgraph isomorphic to H. A graph is called Ni-locally connected if G[{x∈V(G):1≤dG(w,x)≤i}] is connected and N2-locally connected if G[{uv:{uw,vw}⊆E(G)}] is connected for every vertex w of G, respectively. In this paper, we prove the following.Every 2-connected P7-free graph of minimum degree at least three other than the Petersen graph has a spanning Eulerian subgraph. This implies that every H-free 3-connected graph (or connected N4-locally connected graph of minimum degree at least three) other than the Petersen graph is supereulerian if and only if H is an induced subgraph of P7, where Pi is a path of i vertices.Every 2-edge-connected H-free graph other than {K2,2k+1:kis a positive integer} is supereulerian if and only if H is an induced subgraph of P4.If every connected H-free N3-locally connected graph other than the Petersen graph of minimum degree at least three is supereulerian, then H is an induced subgraph of P7 or T2,2,3, i.e., the graph obtained by identifying exactly one end vertex of P3,P3,P4, respectively.If every 3-connected H-free N2-locally connected graph is hamiltonian, then H is an induced subgraph of K1,4. We present an algorithm to find a collapsible subgraph of a graph with girth 4 whose idea is used to prove our first conclusion above. Finally, we propose that the reverse of the last two items would be true. [ABSTRACT FROM AUTHOR]

We consider several extremal problems of maximizing the number of colorings and independent sets in some graph families with fixed chromatic number and order. First, we address the problem of maximizing the number of colorings in the family of connected graphs with chromatic number k and order n where k≥4. It was conjectured that extremal graphs are those which have clique number k and size k2+n-k. We affirm this conjecture for 4-chromatic claw-free graphs and for all k-chromatic line graphs with k≥4. We also reduce this extremal problem to a finite family of graphs when restricted to claw-free graphs. Secondly, we determine the maximum number of independent sets of each size in the family of n-vertex k-chromatic graphs (respectively connected n-vertex k-chromatic graphs and n-vertex k-chromatic graphs with c components). We show that the unique extremal graph is Kk∪En-k, K1∨(Kk-1∪En-k) and (K1∨(Kk-1∪En-k-c+1))∪Ec-1 respectively. [ABSTRACT FROM AUTHOR]

For an edge e of a given graph G, define ce(G) be the length of a longest cycle of G containing e. Wang and Lv (2008) gave a tight function f0(n,k) (for integers n≥3 and k≥4), such that for any 2-connected graph G on n vertices with more than f0(n,k) edges, every edge belongs to a cycle of length at least k, i.e., ce(G)≥k for every edge e∈E(G). In this work we give a tight function f(n, k) (for integers n≥k≥6), such that for any 2-connected graph G on n vertices with more than f(n, k) edges, we have that ce(G)≥k for all but at most one edge of G. [ABSTRACT FROM AUTHOR]

There are typically several nonisomorphic graphs having a given degree sequence, and for any two degree sequence terms it is often possible to find a realization in which the corresponding vertices are adjacent and one in which they are not. We provide necessary and sufficient conditions for two vertices to be adjacent (or nonadjacent) in every realization of the degree sequence. These conditions generalize degree sequence and structural characterizations of the threshold graphs, in which every adjacency relationship is forcibly determined by the degree sequence. We further show that degree sequences for which adjacency relationships are forced form an upward-closed set in the dominance order on graphic partitions of an even integer. [ABSTRACT FROM AUTHOR]

A bipartition of the vertex set of a graph is called balanced if the sizes of the sets in the bipartition differ by at most one. Bolloba´s and Scott proved that every regular graph with m edges admits a balanced bipartition V1, V2 of V(G) such that max{e(V1),e(V2)}

We consider latin square graphs Γ=LSG(H) of the Cayley table of a given finite group H. We characterize all pairs (Γ,G), where G is a subgroup of autoparatopisms of the Cayley table of H such that G acts arc-transitively on Γ and all nontrivial G-normal quotient graphs of Γ are complete. We show that H must be elementary abelian and determine the number k of complete normal quotients. This yields new infinite families of diameter two arc-transitive graphs with k=1 or k=2. [ABSTRACT FROM AUTHOR]

The independence polynomialI(G, x) of a finite graph G is the generating function for the sequence of the number of independent sets of each cardinality. We investigate whether, given a fixed number of vertices and edges, there exists optimally-least (optimally-greatest) graphs, that are least (respectively, greatest) for all non-negative x. Moreover, we broaden our scope to k-independence polynomials, which are generating functions for the k-clique-free subsets of vertices. For k≥3, the results can be quite different from the k=2 (i.e. independence) case. [ABSTRACT FROM AUTHOR]

We consider the so-called coupon-coloring of the vertices of a graph where every color appears in every open neighborhood, and our aim is to determine the maximal number of colors in such colorings. In other words, every color class must be a total dominating set in the graph and we study the total domatic number of the graph. We determine this parameter in every maximal outerplanar graph, and show that every Hamiltonian maximal planar graph has domatic number at least two, partially answering the conjecture of Goddard and Henning. [ABSTRACT FROM AUTHOR]

The eigenvalues of a graph are algebraic integers in some algebraic extension of the rationals. We investigate the algebraic degree of these eigenvalues with respect to graph-theoretical properties. We obtain quantitative results showing that a graph with large diameter must have some eigenvalues of large algebraic degree. [ABSTRACT FROM AUTHOR]

It is well-known that there exists a triangle-free planar graph of n vertices that has the largest induced forest of order at most 5n8. Salavatipour (Graphs Comb 22(1):113-126, 2006) proved that there is a forest of order at least 5n9.41 in any triangle-free planar graph of n vertices. Dross et al. (Large induced forests in planar graphs with girth 4 or 5, arXiv:1409.1348, 2014) improved Salavatipour’s bound to 5n9.17. In this work, we further improve the bound to 5n9. Our technique is inspired by the recent ideas from Lukot’ka et al. (Electron J Comb 22(1):P1-P11, 2015). [ABSTRACT FROM AUTHOR]

We prove that for any integers p≥k≥3 and any k-tuple of positive integers (n1,…,nk) such that p=∑i=1kni and n1≥n2≥⋯≥nk, the condition n1≤p2 is necessary and sufficient for every subgraph of the complete k-partite graph K(n1,…,nk) with at least 4-2p+2n1+∑i=1kni(p-ni)2edges to be chorded pancyclic. Removing all but one edge incident with any vertex of minimum degree in K(n1,…,nk) shows that this result is best possible. Our result implies that for any integers, k≥3 and n≥1, a balanced k-partite graph of order kn with has at least (k2-k)n2-2n(k-1)+42 edges is chorded pancyclic. In the case k=3, this result strengthens a previous one by Adamus, who in 2009 showed that a balanced tripartite graph of order 3n, n≥2, with at least 3n2-2n+2 edges is pancyclic. [ABSTRACT FROM AUTHOR]

Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed k≥1, among all graphs on n vertices with e edges, some threshold graph has the fewest matchings of size k; indeed either the lex graph or the colex graph is such an extremal example. In this paper we consider the problem of maximizing the number of matchings in the class of threshold graphs. We prove that the minimizers are what we call almost alternating threshold graphs. We also discuss a problem with a similar flavor: which threshold graph has the fewest independent sets. Here we are inspired by the result that among all graphs on n vertices and e edges the lex graph has the most independent sets. [ABSTRACT FROM AUTHOR]

Let G be an infinite family of connected graphs and let k be a positive integer. We say that k is forcing for G if for all G∈G but finitely many, the following holds. Any {-1,1}-weighing of the edges of G for which all connected subgraphs on k edges are positively weighted implies that G is positively weighted. Otherwise, we say that it is weakly forcing for G if any such weighing implies that the weight of G is bounded from below by a constant. Otherwise we say that kcollapses for G. We classify k for some of the most prominent classes of graphs, such as all connected graphs, all connected graphs with a given maximum degree and all connected graphs with a given average degree. [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]

One-overlapped factorizations of finite groups were introduced by Shinohara (Linear Algebra Appl. 436(4):850-857, 2012) for constructing a new class of thin Lehman matrices. However, all known examples and constructions arise from cyclic or dihedral groups. In this paper, we prove the existence of one-overlapped factorizations of non-abelian groups that are not dihedral and describe a simple construction. The corresponding incidence structures and Lehman matrices are also considered. [ABSTRACT FROM AUTHOR]

A dynamic coloring of the vertices of a graph G starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set (zero forcing set) of G if, by iteratively applying the forcing process, every vertex in G becomes colored. If the initial set S has the added property that it induces a subgraph of G without isolated vertices, then S is called a total forcing set in G. The total forcing number of G, denoted Ft(G), is the minimum cardinality of a total forcing set in G. We prove that if G is a connected, claw-free, cubic graph of order n≥6, then Ft(G)≤12n, where a claw-free graph is a graph that does not contain K1,3 as an induced subgraph. The graphs achieving equality in these bounds are characterized. [ABSTRACT FROM AUTHOR]

An edge k-weighting of a graph G=(V,E) is a function l:E→{1,⋯,k}. For v∈V we denote by S(v) the multiset of weights on edges incident to v. We say that a weighting l induces a vertex coloring via a function f if f(S(v))≠f(S(u)) for all adjacent vertices u,v∈V. One corresponding coloring parameter is χf(G), the f-neighbor-distinguishing index. It is the smallest value k such that a k-weighting induces a vertex coloring of G via f. In literature, several functions f, e.g., sums and products, and different additional constraints for the colorings have been studied. Thereby a lot of related coloring parameters arise. In this note, we introduce a class of functions, so-called dispersing functions. We prove bounds for three classes of coloring parameters, which are induced by edge weightings via arbitrary dispersing functions. [ABSTRACT FROM AUTHOR]

For graphs G and H and integer k≥1, the Gallai-Ramsey number grk(G:H) is defined to be the minimum integer N such that if KN is edge-colored with k colors, then there is either a rainbow G or a monochromatic H. It is known that grk(K3:C2n+1) is exponential in k. In this note, we improve the upper bound for grk(K3:C2n+1) obtained by Hall et al., and give bounds for grk(K3:Km,n). [ABSTRACT FROM AUTHOR]

We consider a game played on an initially empty graph where two players alternate drawing an edge between vertices subject to the condition that no degree can exceed k. We show that for k=3, either player can avoid a Hamilton cycle, and for k≥4, either player can force the resulting graph to be Hamiltonian. [ABSTRACT FROM AUTHOR]

Let G be a 4-connected graph, and let E~(G) denote the set of those edges of G which are not contained in a triangle and let Ec(G) denote the set of 4-contractible edges of G. We show that if |E~(G)|≥1, then |Ec(G)|≥(|E~(G)|+8)/4 unless G has one of the specified configurations. [ABSTRACT FROM AUTHOR]

A hole is an induced cycle with at least four vertices. A hole is even if it has an even number of vertices. Even-hole-free graphs are being actively studied in the literature. It is not known whether even-hole-free graphs can be optimally colored in polynomial time. A diamond is the graph obtained from the clique of four vertices by removing one edge. A kite is a graph consists of a diamond and another vertex adjacent to a vertex of degree two in the diamond. Kloks et al. (J Combin Theory B 99:733-800, 2009) designed a polynomial-time algorithm to color an (even hole, diamond)-free graph. In this paper, we consider the class of (even hole, kite)-free graphs which generalizes (even hole, diamond)-free graphs. We prove that a connected (even hole, kite)-free graph is diamond-free, or the join of a clique and a diamond-free graph, or contains a clique cutset. This result, together with the result of Kloks et al., imply the existence of a polynomial time algorithm to color (even hole, kite)-free graphs. We also prove (even hole, kite)-free graphs are β-perfect in the sense of Markossian, Gasparian and Reed. Finally, we establish the Vizing bound for (even hole, kite)-free graphs. [ABSTRACT FROM AUTHOR]

A generalization of the Oberwolfach problem, proposed by Liu (J Comb Des 8:42-49, 2000), asks for a uniform 2-factorization of the complete multipartite graph Km×n. Here we focus our attention on cyclic 2-factorizations, whose 2-factors are disjoint union of cycles all of even length ℓ. In particular, we present a complete solution for the extremal cases ℓ=4 and ℓ=mn. [ABSTRACT FROM AUTHOR]

The Johnson graph J(n, m) has the m-subsets of {1,2,…,n} as vertices and two subsets are adjacent in the graph if they share m-1 elements. Shapozenko asked about the isoperimetric function μn,m(k) of Johnson graphs, that is, the cardinality of the smallest boundary of sets with k vertices in J(n, m) for each 1≤k≤nm. We give an upper bound for μn,m(k) and show that, for each given k such that the solution to the Shadow Minimization Problem in the Boolean lattice is unique, and each sufficiently large n, the given upper bound is tight. We also show that the bound is tight for the small values of k≤m+1 and for all values of k when m=2. [ABSTRACT FROM AUTHOR]

For an undirected simple graph G, we write G→(H1,H2)v if and only if for everyred-blue coloring of its vertices there exists a red H1 or a blue H2. Thegeneralized vertex Folkman number Fv(H1,H2;H) is defined as the smallest integer n for which there exists an H-free graph G of order n such that G→(H1,H2)v. The generalized edge Folkman numbers Fe(H1,H2;H) are defined similarly, when colorings of the edges are considered. We show that Fe(Kk+1,Kk+1;Kk+2-e) and Fv(Kk,Kk;Kk+1-e) are well defined for k≥3. We prove the nonexistence of Fe(K3,K3;H) for some H, in particular for H=B3, where Bk is the book graph of k triangular pages, and for H=K1+P4. We pose three problems ongeneralized Folkman numbers, including the existence question of edge Folkmannumbers Fe(K3,K3;B4), Fe(K3,K3;K1+C4) and Fe(K3,K3;P2∪P3¯). Our results lead to some general inequalities involving two-color and multicolor Folkmannumbers. [ABSTRACT FROM AUTHOR]

The maximum independent sets in the Doob graphs D(m, n) are analogs of the distance-2 MDS codes in Hamming graphs and of the latin hypercubes. We prove the characterization of these sets stating that every such set is semilinear or reducible. As related objects, we study vertex sets with maximum cut (edge boundary) in D(m, n) and prove some facts on their structure. We show that the considered two classes (the maximum independent sets and the maximum-cut sets) can be defined as classes of completely regular sets with specified 2-by-2 quotient matrices. It is notable that for a set from the considered classes, the eigenvalues of the quotient matrix are the maximum and the minimum eigenvalues of the graph. For D(m, 0), we show the existence of a third, intermediate, class of completely regular sets with the same property. [ABSTRACT FROM AUTHOR]

A real number α∈[0,1) is a jump for an integer r≥2 if there exists a constant c>0 such that any number in (α,α+c] cannot be the Turán density of a family of r-uniform graphs. Erdős and Stone showed that every number in [0,1) is a jump for r=2. Erdős asked whether the same is true for r≥3. Frankl and Rödl gave a negative answer by showing the existence of non-jumps for r≥3. Recently, Baber and Talbot showed that every number in [0.2299,0.2316)⋃[0.2871,827) is a jump for r=3 using Razborov’s flag algebra method. Pikhurko showed that the set of non-jumps for every r≥3 has cardinality of the continuum. But, there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we show that 1+r-1lr-1-rlr-2 is a non-jump for r≥4 and l≥3 which generalizes some earlier results. We do not know whether the same result holds for r=3. In fact, when r=3 and l=3, 1+r-1lr-1-rlr-2=29, and determining whether 29 is a jump or not for r=3 is perhaps the most important unknown question regarding this subject. Erdős offered $500 for answering this question. [ABSTRACT FROM AUTHOR]

The total domination game is a two-person competitive optimization game, where the players, Dominator and Staller, alternately select vertices of an isolate-free graph G. Each vertex chosen must strictly increase the number of vertices totally dominated. This process eventually produces a total dominating set of G. Dominator wishes to minimize the number of vertices chosen in the game, while Staller wishes to maximize it. The game total domination number of G, γtg(G), is the number of vertices chosen when Dominator starts the game and both players play optimally. Recently, Henning, Klavžar, and Rall proved that γtg(G)≤45n holds for every graph G which is given on n vertices such that every component of it is of order at least 3; they also conjectured that the sharp upper bound would be 34n. Here, we prove that γtg(G)≤1114n holds for every G which contains no isolated vertices or isolated edges. [ABSTRACT FROM AUTHOR]

A b-coloring of the vertices of a graph is a proper coloring where each color class contains a vertex which is adjacent to each other color class. The b-chromatic number of G is the maximum integer $$b(G)$$ for which G has a b-coloring with $$b(G)$$ colors. A graph G is b-continuous if G has a b-coloring with k colors, for every integer k in the interval $$[\chi (G),b(G)]$$ . It is known that not all graphs are b-continuous, and that it is NP-complete to decide whether a given graph G is b-continuous even if $$\chi (G)$$ and $$b(G)$$ are known. Also, there are many results that show that finding b-colorings of graphs with large girth is an easier task. For instance, finding $$b(G)$$ can be done in polynomial time when G has girth at least 7; also, regular graphs with girth at least 8 are b-continuous. In this article, we show that if G has girth at least 10, then G is b-continuous. [ABSTRACT FROM AUTHOR]

The power index $$\Theta (\Gamma )$$ of a graph $$\Gamma $$ is the least order of a group G such that $$\Gamma $$ can embed into the power graph of G. Furthermore, this group G is $$\Gamma $$ -optimal if G has order $$\Theta (\Gamma )$$ . We say that $$\Gamma $$ is power-critical if its order is equal to $$\Theta (\Gamma )$$ . This paper focuses on the power indices of complete graphs, complete bipartite graphs and 1-factors. We classify all power-critical graphs $$\Gamma '$$ in these three families, and give a necessary and sufficient condition for $$\Gamma '$$ -optimal groups. [ABSTRACT FROM AUTHOR]

Codes from neighbourhood designs of generalized Paley graphs $$GP(q,k)$$ of a finite field of order q and their complements are investigated. With certain q and k, we obtain the main parameters of such codes and their duals including bases of minimum-weight vectors for the codes. [ABSTRACT FROM AUTHOR]