Search

Given a graph G and an integer k, the k-Biclique problem asks whether G contains a complete bipartite subgraph with k vertices on each side. Whether there is an f(k) ċ |G|O(1)-time algorithm, solving k-Biclique for some computable function f has been a longstanding open problem. We show that k-Biclique is W[1]-hard, which implies that such an f(k) ċ |G|O(1)-time algorithm does not exist under the hypothesis W[1] ≠ FPT from parameterized complexity theory. To prove this result, we give a reduction which, for every n-vertex graph G and small integer k, constructs a bipartite graph H = (L⊍ R,E) in time polynomial in n such that if G contains a clique with k vertices, then there are k(k − 1)/2 vertices in L with nθ(1/k) common neighbors; otherwise, any k(k − 1)/2 vertices in L have at most (k+1)! common neighbors. An additional feature of this reduction is that it creates a gap on the right side of the biclique. Such a gap might have further applications in proving hardness of approximation results. Assuming a randomized version of Exponential Time Hypothesis, we establish an f(k) ċ |G|o(&sqrt;k)-time lower bound for k-Biclique for any computable function f. Combining our result with the work of Bulatov and Marx [2014], we obtain a dichotomy classification of the parameterized complexity of cardinality constraint satisfaction problems. [ABSTRACT FROM AUTHOR]

In this paper, we study the recently introduced scoring game played on graphs called the Edge-Balanced Index Game. This game is played on a graph by two players, Alice and Bob, who take turns colouring an uncoloured edge of the graph. Alice plays first and colours edges red, while Bob colours edges blue. The game ends once all the edges have been coloured. A player captures a vertex if more than half of its incident edges are coloured by that player, and the player that captures the most vertices wins. Using classical arguments from the field, we first prove general properties of this game. Namely, we prove that there is no graph in which Bob can win (if Alice plays optimally), while Alice can never capture more than 2 more vertices than Bob (if Bob plays optimally). Through dedicated arguments, we then investigate more specific properties of the game, and focus on its outcome when played in particular graph classes. Specifically, we determine the outcome of the game in paths, cycles, complete bipartite graphs, and Cartesian grids, and give partial results for trees and complete graphs. [ABSTRACT FROM AUTHOR]

This paper is concerned with calculating the Möbius index values and arrived results for a few standard graphs. Some standard graphs which we considered are Path graph, Cycle graph, Complete Graph, Star Graph, Shell graph, Wheel Graph, Gear graph, Helm Graph, the Web graph, Flower Graph. [ABSTRACT FROM AUTHOR]

A graph G is a common multiple of two graphs H1 and H2 if there exists a decomposition of G into edge-disjoint copies of H1 and also a decomposition of G into edge-disjoint copies of H2. If G is a common multiple of H1 and H2, and G has q edges, then we call G a (q;H1;H2) graph. Our paper deals with the following question: Given two graphs H1 and H2, for which values of q does there exist a (q;H1;H2) graph? when H1 is either a path or a star or a cycle and H2 is a complete bipartite graph. [ABSTRACT FROM AUTHOR]

Let G be either a complete graph of odd order or a complete bipartite graph in which each vertex partition has an even number of vertices. In this paper, we determine the set of triples (p, q, r), with p, q, r > 0, for which there exists a decomposition of G into p paths, q stars, and r cycles, each of which has 4 edges. [ABSTRACT FROM AUTHOR]

For any finite simple undirected graph G = (V (G) , E (G)) , we consider the binary relation ← G on the powerset 𝒫 (V (G)) of its vertex set given by B ← G A if ⋂ v ∈ B N G (v) ⊇ ⋂ v ∈ A N G (v) , where N G (v) denotes the neighborhood of a vertex v. We call the above relation set adiacence dependency (sa)-dependency of G. With the relation ← G we associate an intersection-closed family C L s a (G) of vertex subsets and the corresponding induced lattice ℭ (G) : = (C L s a (G) , ⊆) , which we call sa-lattice of G. Through the equality of sa-lattices, we introduce an equivalence relation ≡ s a between graphs and propose three different classifications of graphs based on such a relation. Furthermore, we determine the sa-lattice for various graph families, such as complete graphs, complete bipartite graphs, cycles and paths and, next, we study such a lattice in relation to the Cartesian and the tensor product of graphs, verifying that in most cases it is a graded lattice. Finally, we provide two algorithms, namely, the T-DI ALGORITHM and the O-F ALGORITHM, in order to provide two different computational ways to construct the sa-lattice of a graph. For the O-F ALGORITHM we also determine its computational complexity. [ABSTRACT FROM AUTHOR]

In any interconnection network, task allocation plays a major role in the processor speed as fair distribution leads to enhanced performance. Complete multipartite networks serve well for this purpose as the task can be split into different partites which improves the degree of reliability of the network. Such an allocation process in the network can be done by means of graph embedding. The optimal wirelength of a graph embedding helps in the distribution of deterministic algorithms from the guest graph to other host graphs in order to incorporate its unique deterministic properties on that chosen graph. In this paper, we propose an algorithm to compute the optimal wirelength of balanced complete multipartite graphs onto the Cartesian product of trees with path and cycle. Moreover, we derive the closed formulae for wirelengths in specific trees like (1-rooted) complete binary tree and sibling graphs. [ABSTRACT FROM AUTHOR]

An interconnection network is a complex connection of a set of processors and communication links between different processors which is utilized to exchange data between processors in the parallel computing system. Graph embedding is a vital tool used to run parallel algorithms in computer networks in which placing different modules on the board is one of the main cost criteria. By finding the optimal layout, the placement problem in circuit designs which does not have any deterministic algorithms can be solved. The complete multipartite graph is a widely used network topology with a high degree of reliability due to its flexible choice of network size. Recently a study was made by computing the optimal layout of balanced complete multipartite graphs into host graphs taken from the Cartesian product of elements in the set {path, cycle}, but leaving the case of product of paths as an open problem. This paper aims to solve such an open problem and the key idea is to locate suitable optimal sets in balanced complete multipartite graphs with respect to maximizing the number of edges in the located sets. Besides, we compute the layout in the case of host graphs like k -rooted complete binary trees, k -rooted sibling trees and the Cartesian product of path P 2 and complete binary trees. [ABSTRACT FROM AUTHOR]

Let G be a connected simple graph. A graph H is said to be a m-Super subdivision of G, if every edge of G is replaced by the complete bipartite graph Km,m with m > 2 in such a way that the end vertices of the edge are merged with any two vertices of the same partite set A or B of Km,m after removal of the edge of G. In this paper, we prove that m-Super subdivision of path and cycle are graceful. [ABSTRACT FROM AUTHOR]

Let H be a graph. A decomposition of H is a set of edge-disjoint sub- graphs of H whose union is H. A Hamiltonian path (respectively, cycle) of H is a path (respectively, cycle) that contains every vertex of H exactly once. A k-star, denoted by Sk, is a star with k edges. In this paper, we give necessary and sufficient conditions for decomposing the complete graph into α copies of Hamiltonian path (cycle) and β copies of S3. [ABSTRACT FROM AUTHOR]

Let Γ = (G, σ) be a signed graph, where G is the underlying simple graph and σ : E(G) → {--, +} is the sign function on the edges of G. The adjacency matrix of a signed graph has -1 or +1 for adjacent vertices, depending on the sign of the edges. It was conjectured that if Γ is a signed complete graph of order n with k negative edges, k < n -- 1 and Γ has maximum index, then negative edges form K1,k. In this paper, we prove this conjecture if we confine ourselves to all signed complete graphs of order n whose negative edges form a tree of order k + 1. A [1, 2]-subgraph of G is a graph whose components are paths and cycles. Let Γ be a signed complete graph whose negative edges form a [1, 2]-subgraph. We show that the eigenvalues of Γ satisfy the following inequalities: --5 ≤ λn ≤ ... ≤ λ2 ≤ 3. [ABSTRACT FROM AUTHOR]

A subgraph of an edge‐colored graph is said to be properly colored, or shortly PC, if any two adjacent edges have different colors. Fujita, Li, and Zhang gave a decomposition theorem for edge‐colorings of complete bipartite graphs without PC C4. However, their decomposition just focuses on a local structure. In this paper, we give a new and global decomposition theorem for edge‐colorings of complete bipartite graphs without PC C4. Our decomposition gives a corollary on the existence of a monochromatic star with almost sharp bound. [ABSTRACT FROM AUTHOR]

A star coloring of a graph G is a proper vertex coloring in which every path on four vertices in G is not bicolored. The star chromatic number Xs (G) ofG is the least number of colors needed to star color G. In this paper, we have generalized the star chromatic number of degree splitting of join of any two graph G and H denoted by G + H, where G is a path graph and H is any simple graph. Also, we determine the star chromatic number for degree splitting of join of path graph G of order m with path Pn, complete graph Kn and cyclevgraph Cn. [ABSTRACT FROM AUTHOR]

The k‐color bipartite Ramsey number of a bipartite graph H is the least integer n for which every k‐edge‐colored complete bipartite graph Kn,n contains a monochromatic copy of H. The study of bipartite Ramsey numbers was initiated, over 40 years ago, by Faudree and Schelp and, independently, by Gyárfás and Lehel, who determined the 2‐color Ramsey number of paths. In this paper we determine asymptotically the 3‐color bipartite Ramsey number of paths and (even) cycles. [ABSTRACT FROM AUTHOR]

Abstract An edge-coloured graph G is called properly connected if every two vertices are connected by a proper path. The proper connection number of a connected graph G , denoted by pc (G), is the smallest number of colours that are needed in order to make G properly connected. van Aardt et al. (2017)gave a sufficient condition for the proper connection number to be at most k in terms of the size of graphs. In this note, our main result is the following, by adding a minimum degree condition: let G be a connected graph of order n, k ≥ 3. If | E (G) | ≥ (n − m − (k + 1 − m) (δ + 1) 2) + (k + 1 − m) (δ + 1 2) + k + 2 , then pc (G) ≤ k , where m takes the value k + 1 if δ = 1 and ⌊ k δ − 1 ⌋ if δ ≥ 2. Furthermore, if k = 2 and δ = 2 , pc (G) ≤ 2, except G ∈ { G 1 , G n } (n ≥ 8), where G 1 = K 1 ∨ 3 K 2 and G n is obtained by taking a complete graph K n − 5 and K 1 ∨(2 K 2) with an arbitrary vertex of K n − 5 and a vertex with d (v) = 4 in K 1 ∨(2 K 2) being joined. If k = 2 , δ ≥ 3, we conjecture pc (G) ≤ 2, where m takes the value 1 if δ = 3 and 0 if δ ≥ 4 in the assumption. [ABSTRACT FROM AUTHOR]

We show that any complete k‐partite graph G on n vertices, with k≥3, whose edges are two‐coloured, can be covered with two vertex‐disjoint monochromatic paths of distinct colours, given that the largest partition class of G contains at most n∕2 vertices. This extends known results for complete and complete bipartite graphs. Secondly, we show that in the same situation, all but o(n) vertices of the graph can be covered with two vertex‐disjoint monochromatic cycles of distinct colours, if colourings close to a split colouring are excluded. From this we derive that the whole graph, if large enough, may be covered with 14 vertex‐disjoint monochromatic cycles. [ABSTRACT FROM AUTHOR]

Let P k be a path, C k a cycle on k vertices, and K k , k a complete bipartite graph with k vertices on each side of the bipartition. We prove that (1) for any integers k , t > 0 and a graph H there are finitely many subgraph minimal graphs with no induced P k and K t , t that are not H -colorable and (2) for any integer k > 4 there are finitely many subgraph minimal graphs with no induced P k that are not C k − 2 -colorable. The former generalizes the result of Hell and Huang (2013) and the latter extends a result of Bruce etal. (2009). Both our results lead to polynomial-time certifying algorithms for the corresponding coloring problems. [ABSTRACT FROM AUTHOR]

We show that for every η>0 there exists an integer n0 such that every 2‐coloring of the 3‐uniform complete hypergraph on n≥n0 vertices contains two disjoint monochromatic tight cycles of distinct colors that together cover all but at most ηn vertices. The same result holds if tight cycles are replaced by loose cycles. [ABSTRACT FROM AUTHOR]

The famous Kőnig‐Egerváry theorem is equivalent to the statement that the matching number equals the vertex cover number for every induced subgraph of some graph if and only if that graph is bipartite. Inspired by this result, we consider the set Gk of all graphs such that, for every induced subgraph, the maximum number of disjoint paths of order k equals the minimum order of a set of vertices intersecting all paths of order k. For k∈{3,4}, we give complete structural descriptions of the graphs in Gk. Furthermore, for odd k, we give a complete structural description of the graphs in Gk that contain no cycle of order less than k. For these graph classes, our results yield efficient recognition algorithms as well as efficient algorithms that determine maximum sets of disjoint paths of order k and minimum sets of vertices intersecting all paths of order k. [ABSTRACT FROM AUTHOR]

Let k ⩾ 2 be an integer. We show that if s = 2 and t ⩾ 2, or s = t = 3, then the maximum possible number of edges in a C 2 k +1-free graph containing no induced copy of Ks,t is asymptotically equal to (t − s + 1)1/ s (n /2)2−1/ s except when k = s = t = 2. This strengthens a result of Allen, Keevash, Sudakov and Verstraëte [1], and answers a question of Loh, Tait, Timmons and Zhou [14]. [ABSTRACT FROM AUTHOR]

Abstract For k given graphs G 1 , G 2 , ... , G k , k ≥ 2 , the k -color Ramsey number, denoted by R (G 1 , G 2 , ... , G k) , is the smallest integer N such that if we arbitrarily color the edges of a complete graph of order N with k colors, then it always contains a monochromatic copy of G i colored with i , for some 1 ≤ i ≤ k. Let C m be a cycle of length m and K 1 , n a star of order n + 1. In this paper, firstly we give a general upper bound of R (C 4 , C 4 , ... , C 4 , K 1 , n). In particular, for the 3-color case, we have R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 3 and this bound is tight in some sense. Furthermore, we prove that R (C 4 , C 4 , K 1 , n) ≤ n + 4 n + 5 + 2 for all n = ℓ 2 − ℓ and ℓ ≥ 2 , and if ℓ is a prime power, then the equality holds. [ABSTRACT FROM AUTHOR]

The notion of uniformity, as in uniform 1‐factorisations, extends naturally to graph decompositions generally. The existence of uniform decompositions of complete multigraphs into cycles is investigated and some connections with families of classical designs are established. We show that if there exists a uniform decomposition of μKn into m‐cycles then (A) n=m and n≤7, or (B) μ=2 and m=n−1, or (C) μ=1, m=(n−1)∕2 and n≡3(mod4) or (D) μ=1 and 2m(m+1)=n(n−1). For case A, there are only a few small values of n and μ to consider, and we exhibit all uniform decompositions up to isomorphism for each such n and μ. In each of cases B and C, we construct examples of uniform decompositions for infinitely many values of n, and we investigate the isomorphism classes of our examples for each such n. We have no examples of uniform decompositions in case D, but we rule out the smallest example, namely n=21 and m=14, and we prove that if such decompositions exist, then so do large quasiresidual designs that are not residual. [ABSTRACT FROM AUTHOR]

Abstract DP-coloring (also called correspondence coloring) is a generalization of list coloring recently introduced by Dvořák and Postle. Several known bounds for the list chromatic number of a graph G , χ ℓ (G) , also hold for the DP-chromatic number of G , χ D P (G). On the other hand, there are several properties of the DP-chromatic number that show that it differs with the list chromatic number. In this note we show one such property. It is well known that χ ℓ (K k , t) = k + 1 if and only if t ≥ k k. We show that χ D P (K k , t) = k + 1 if t ≥ 1 + (k k ∕ k !) (log (k !) + 1) , and we show that χ D P (K k , t) < k + 1 if t < k k ∕ k !. [ABSTRACT FROM AUTHOR]

Abstract We introduce the family of k-gap-planar graphs for k ≥ 0 , i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most k of its crossings. This definition is motivated by applications in edge casing, as a k -gap-planar graph can be drawn crossing-free after introducing at most k local gaps per edge. We present results on the maximum density of k -gap-planar graphs, their relationship to other classes of beyond-planar graphs, characterization of k -gap-planar complete graphs, and the computational complexity of recognizing k -gap-planar graphs. [ABSTRACT FROM AUTHOR]

The distance matrix, distance eigenvalue, and distance energy of a connected graph have been studied intensively in the literature. We propose a new problem of studying how the distance energy changes when an edge is deleted. In this paper, we prove that the distance energy of a complete bipartite graph is always increased when an edge is deleted. [ABSTRACT FROM AUTHOR]

The amalgamation of several graphs is obtained by identifying one vertex from each graph as the same vertex. A graph can be represented by matrices, such as adjacency matrix, anti-adjacency matrix, and Laplacian matrix. In this paper we compute the characteristic polynomials of the adjacency, anti-adjacency, and Laplacian matrices of the amalgamation of two complete graphs. [ABSTRACT FROM AUTHOR]

The p-competition graph Cp(D) of a digraph D = (V,A) is a graph with V (Cp(D)) = V (D), where an edge between distinct vertices x and y if and only if there exist p distinct vertices v1, v2, ..., vp 2 V such that x → vi, y → vi are arcs of the digraph D for each i = 1, 2, ..., p. In this paper, we obtain that a path with order n ≥ 6 is a p-competition graph if and only if n ≥ p + 3. We also show that for a p-competition graph G with no isolated vertices, G+Kn is a p+n-competition graph. And we obtain that a wheel Wn is a p-competition graph if and only if n ≥ p + 3. [ABSTRACT FROM AUTHOR]

Given t distinct colors, we order the t subsets of t - 1 colors in some arbitrary manner. Let G1, G2, . . ., Gt be graphs. The (t - 1)-chromatic Ramsey number, denoted by γt t-1(G1, G2, . . ., Gt), is defined to be the least number n such that if the edges of the complete graph Kn are colored in any fashion with t colors, then for some i the subgraph whose edges are colored with the ith subset of colors contains a Gi. In this paper, we find the value of γ5 4(G1, . . ., G5) when each Gi is a path. [ABSTRACT FROM AUTHOR]

The Möbius coinvariant μ ⊥ ( G ) of a graph G is defined to be the Möbius invariant of the dual of the cycle matroid of G . This invariant is known to equal the rank of the reduced homology of the cycle matroid complex of G . For a complete graph K m + 1 , W. Kook gave an interpretation of μ ⊥ ( K m + 1 ) as the number of edge-rooted forests in K m . In this paper, we obtain a new combinatorial interpretation of μ ⊥ ( K m + 1 , n + 1 ) as the number of B-edge-rooted forests in K m , n , which is a bipartite analogue of the previous result. Based on these interpretations, we will give new bijective proofs of the formulas for μ ⊥ ( K m + 1 ) and μ ⊥ ( K m + 1 , n + 1 ) given by I. Novik, A. Postnikov, and B. Sturmfels in terms of the Hermite polynomials. In addition, we will construct a homology basis for the cycle matroid complex of K m + 1 , n + 1 indexed by the B-edge-rooted forests. Also we will discuss the Möbius coinvariant of bi-coned graphs which generalize complete bipartite graphs. [ABSTRACT FROM AUTHOR]

We show that for all ℓ , k , n with ℓ ≤ k ∕ 2 and ( k − ℓ ) dividing n the following hypergraph-variant of Lehel’s conjecture is true. Every 2-edge-colouring of the k -uniform complete hypergraph K n ( k ) on n vertices has at most two disjoint monochromatic ℓ -cycles in different colours that together cover all but at most 4 ( k − ℓ ) vertices. If ℓ ≤ k ∕ 3 , then at most two ℓ -cycles cover all but at most 2 ( k − ℓ ) vertices. Furthermore, we can cover all vertices with at most 4 (3 if ℓ ≤ k ∕ 3 ) disjoint monochromatic ℓ -cycles. [ABSTRACT FROM AUTHOR]

We show that there exists an absolute constant A such that for each k ≥ 2 and every coloring of the edges of the complete k -uniform hypergraph on A r vertices with r colors, r ≥ r k , one of the color classes contains a loose path of length three. [ABSTRACT FROM AUTHOR]

Let K v ∗ denote the complete graph K v if v is odd and K v − I , the complete graph with the edges of a 1-factor removed, if v is even. Given non-negative integers v , M , N , α , β , the Hamilton–Waterloo problem asks for a 2-factorization of K v ∗ into α C M -factors and β C N -factors. Clearly, M , N ≥ 3 , M ∣ v , N ∣ v and α + β = ⌊ v − 1 2 ⌋ are necessary conditions. Very little is known on the case where M and N have different parities. In this paper, we make some progress on this case by showing, among other things, that the above necessary conditions are sufficient whenever M | N , v > 6 N > 36 M , and β ≥ 3 . [ABSTRACT FROM AUTHOR]

Abstract: An immersion of a graph H in another graph G is a one‐to‐one mapping ϕ : V ( H ) → V ( G ) and a collection of edge‐disjoint paths in G, one for each edge of H, such that the path P u v corresponding to the edge u v has endpoints ϕ ( u ) and ϕ ( v ). The immersion is strong if the paths P u v are internally disjoint from ϕ ( V ( H ) ). We prove that every simple graph of minimum degree at least 11 t + 7 contains a strong immersion of the complete graph K t. This improves on previously known bound of minimum degree at least 200t obtained by DeVos et al. Our result supports a conjecture of Lescure and Meyniel (also independently proposed by Abu‐Khzam and Langston), which is the analogue of famous Hadwiger’s conjecture for immersions and says that every graph without a K t‐immersion is ( t − 1 )‐colorable. [ABSTRACT FROM AUTHOR]

Abstract: We study graphs where each edge that is incident to a vertex of small degree (of degree at most 7 and 9, respectively) belongs to many triangles (at least 4 and 5, respectively) and show that these graphs contain a complete graph (K6 and K7, respectively) as a minor. The second case settles a problem of Nevo. Moreover, if each edge of a graph belongs to six triangles, then the graph contains a K8‐minor or contains K2, 2, 2, 2, 2 as an induced subgraph. We then show applications of these structural properties to stress freeness and coloring of graphs. In particular, motivated by Hadwiger's conjecture, we prove that every K7‐minor free graph is 8‐colorable and every K8‐minor free graph is 10‐colorable. [ABSTRACT FROM AUTHOR]

Let λKv be the complete graph on v vertices in which each pair of vertices is joined by exactly λ edges. An m-cycle system of λKv is a collection C of cycles of length m whose edges partition the edges of λKv. An m-cycle system C of λKv is said to be resolvable if the m-cycles in C can be partitioned into parallel classes R={R1,R2,…,Rλ(v-1)/2} and C is denoted by (v,m,λ)-RCS, R is called a resolution. If a (v,m,λ)-RCS has a pair of orthogonal resolutions, it is said to be doubly resolvable and is denoted by (v,m,λ)-DRCS. In this paper, applying direct constructions and recursive constructions, we show that a (v, 4, 2)-DRCS exists if and only if v≡0(mod4). [ABSTRACT FROM AUTHOR]

An edge colouring of a graph G is complete if for any distinct colours c1 and c2 one can find in G adjacent edges coloured with c1 and c2, respectively. The pseudoachromatic index of G is the maximum number of colours in a complete edge colouring of G. Let ψ(n) denote the pseudoachromatic index of Kn. In the paper we proved that if x≥2 is an integer and n∈{4x2-x,⋯,4x2+3x-3}, then ψ(n)≤2x(n-x-1). Let q be an even integer and let ma=(q+1)2-a. If there is a projective plane of order q, a complete edge colouring of Kma with (ma-a)q colours, a∈{-1,0,⋯,q2+1}, is presented. The main result states that if q≥4 is an integer power of 2, then ψ(ma)=(ma-a)q for any a∈{-1,0,⋯,1+4q+92-1}. [ABSTRACT FROM AUTHOR]

Let G of order n be the vertex-disjoint union of two cycles. It is known that there exists a G -decomposition of K v for all v ≡ 1 ( mod 2 n ) . If G is bipartite and x is a positive integer, it is also known that there exists a G -decomposition of K n x − I , where I is a 1-factor. If G is not bipartite, there exists a G -decomposition of K n if n is odd, and of K n − I , where I is a 1-factor, if n is even. We use novel extensions of the Bose construction for Steiner triple systems and some recent results on the Oberwolfach Problem to obtain a G -decomposition of K v for all v ≡ n ( mod 2 n ) when n is odd, unless G = C 4 ∪ C 5 and v = 9 . If G consists of two odd cycles and n ≡ 0 ( mod 4 ) , we also obtain a G -decomposition of K v − I , for all v ≡ 0 ( mod n ) , v ≠ 4 n . [ABSTRACT FROM AUTHOR]

In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let G be a graph and L(G) be the set of all odd cycle lengths of G. We prove that (1) if L(G) = f3; 3 + 2lg, where l ≥ 2, then x(G) = maxf3; !(G)g, and (2) if L(G) = fk; k + 2lg, where k ≥ 5 and l ≥ 1, then x(G) = 3. These, together with the case L(G) = f3; 5g solved in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072] give a complete solution to the general problem addressed in [S.-S. Wang, SIAM J. Discrete Math., 22 (2008), pp. 1040{1072; S.-M. Camacho and I. Schiermeyer, Discrete Math., 309 (2009), pp. 4916{4919; and T. Kaiser, O. Rucký, and R. Škrekovski, SIAM J. Discrete Math., 25 (2011), pp. 1069{1088]. Our results also improve a classical theorem of Gyárfás which asserts that x (G) ≤ 2jL(G)j + 2 for any graph G. [ABSTRACT FROM AUTHOR]

We consider a generalisation of the classical Ramsey theory setting to a setting where each of the edges of the underlying host graph is coloured with a set of colours (instead of just one colour). We give bounds for monochromatic tree covers in this setting, both for an underlying complete graph, and an underlying complete bipartite graph. We also discuss a generalisation of Ramsey numbers to our setting and propose some other new directions. Our results for tree covers in complete graphs imply that a stronger version of Ryser’s conjecture holds for k -intersecting r -partite r -uniform hypergraphs: they have a transversal of size at most r − k . (Similar results have been obtained by Király et al., see below.) However, we also show that the bound r − k is not best possible in general. [ABSTRACT FROM AUTHOR]

A non-complete distance-regular graph is called geometric if there exists a set C of Delsarte cliques such that each edge lies in exactly one clique in C . Let Γ be a geometric distance-regular graph with diameter D ≥ 3 and smallest eigenvalue θ D . In this paper we show that if Γ contains an induced subgraph K 2 , 1 , 1 , then D ≤ − θ D . Moreover, if − θ D − 1 ≤ D ≤ − θ D then D = − θ D and Γ is a Johnson graph. We also show that for ( s , b ) ⁄ ∈ { ( 11 , 11 ) , ( 21 , 21 ) } , there are no distance-regular graphs with intersection array { 4 s , 3 ( s − 1 ) , s + 1 − b ; 1 , 6 , 4 b } where s , b are integers satisfying s ≥ 3 and 2 ≤ b ≤ s . As an application of these results, we classify geometric distance-regular graphs with D ≥ 3 , θ D ≥ − 4 and containing an induced subgraph K 2 , 1 , 1 . [ABSTRACT FROM AUTHOR]

We study the problem of determining the graph with n vertices having largest signless Laplacian energy. We conjecture it is the complete split graph whose independent set has (roughly) 2 n ∕ 3 vertices. We show that the conjecture is true for several classes of graphs. In particular, the conjecture holds for the set of all complete split graphs of order n , for trees, for unicyclic and bicyclic graphs. We also give conditions on the number of edges, number of cycles and number of small eigenvalues so the graph satisfies the conjecture. [ABSTRACT FROM AUTHOR]

We study ( a : a ) Maker–Breaker games played on the edge set of the complete graph on n vertices. In the following four games — perfect matching game, Hamilton cycle game, star factor game and path factor game, our goal is to determine the least number of moves which Maker needs in order to win these games. Moreover, for all games except for the star factor game, we show how first player can win in the strong version of these games. [ABSTRACT FROM AUTHOR]

The (n, k)-star graphs are an important class of interconnection networks that generalize star graphs, which are superior to hypercubes. In this paper, we continue the work begun by Cheng et al. (Graphs Combin 33(1):85–102, 2017) and complete the classification of all the (n, k)-star graphs that are Cayley. [ABSTRACT FROM AUTHOR]

Let G=H[G1,G2,…,Gk] be the generalized join graph ofG1,G2,…,Gk determined by H. In this paper, we give a decomposition formula for the Bartholdi zeta function of G. As applications, we obtain explicit formulae for Bartholdi zeta functions of some special kinds of graphs, such as the complete multipartite graph, the wheel, etc. [ABSTRACT FROM AUTHOR]

Studies of the p-ary codes from the adjacency matrices of uniform subset graphs Γ(n,k,r) and their reflexive associates have shown that a particular family of codes defined on the subsets are intimately related to the codes from these graphs. We describe these codes here and examine their relation to some particular classes of uniform subset graphs. In particular we include a complete analysis of the p-ary codes from Γ(n,3,r) for p≥5, thus extending earlier results for p=2,3. [ABSTRACT FROM AUTHOR]

Given a graph H, we say a graph G is H-saturated if G does not contain H as a subgraph and the addition of any edge e′∉E(G) results in H as a subgraph. In this paper, we construct (K4-e)-saturated graphs with |E(G)| either the size of a complete bipartite graph, a 3-partite graph, or in the interval 2n-4,n2n2-n+6. We then extend the (K4-e)-saturated graphs to (Kt-e)-saturated graphs. [ABSTRACT FROM AUTHOR]

In this paper we are concerned with the contact process with random recovery rates and edge weights on the complete graph with n vertices. We show that the model has a critical value which is inversely proportional to the product of the mean of the edge weight and the mean of the inverse of the recovery rate. In the subcritical case, the process dies out before an amount of time with order $$O(\log n)$$ with high probability as $$n\rightarrow +\infty $$ . In the supercritical case, the process survives for an amount of time with order $$\exp \{O(n)\}$$ with high probability as $$n\rightarrow +\infty $$ . [ABSTRACT FROM AUTHOR]

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the numbers of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the equitable chromatic number of G and denoted by χ=(G). It is known that the problem of computation of X=(G) is NP-hard in general and remains so for corona graphs. In this paper we consider the same model of coloring in the case of corona multiproducts of graphs. In particular, we obtain some results regarding the equitable chromatic number for the l-corona product G ol H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs are mostly constructive in that they lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G. Moreover, we confirm the Equitable Coloring Conjecture for corona products of such graphs. This paper extends the results from [H. Furmańczyk, K. Kaliraj, M. Kubale and V.J. Vivin, Equitable coloring of corona products of graphs, Adv. Appl. Discrete Math. 11 (2013) 103-120]. [ABSTRACT FROM AUTHOR]

The Hamilton-Waterloo problem asks for which s and r the complete graph [ABSTRACT FROM AUTHOR]

We prove that the complete graph with a hole K u + w − K u can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, each cycle has length at most min ( u , w ) , and the longest cycle is at most three times as long as the second longest. This generalises existing results on decomposing the complete graph with a hole into cycles of uniform length, and complements work on decomposing complete graphs, complete multigraphs, and complete multipartite graphs into cycles of arbitrary specified lengths. [ABSTRACT FROM AUTHOR]