Search

Matt Blum conjectured that the- number of tilings of a hexagonal dungeon with side-lengths a , 2 a , b , a , 2 a , b (for b ≥ 2 a ) equals 1 3 2 a 2 1 4 ⌊ a 2 ∕ 2 ⌋ . Ciucu and the author of the present paper proved the conjecture by using Kuo’s graphical condensation method. In this paper, we investigate a 3-parameter refinement of the conjecture and its application to enumeration of tilings of several new types of the hexagonal dungeons. [ABSTRACT FROM AUTHOR]

A perfect code in a graph Γ = ( V , E ) is a subset C of V that is an independent set such that every vertex in V ∖ C is adjacent to exactly one vertex in C . A total perfect code in Γ is a subset C of V such that every vertex of V is adjacent to exactly one vertex in C . A perfect code in the Hamming graph H ( n , q ) agrees with a q -ary perfect 1-code of length n in the classical setting. In this paper we give a necessary and sufficient condition for a circulant graph of degree p − 1 to admit a perfect code, where p is an odd prime. We also obtain a necessary and sufficient condition for a circulant graph of order n and degree p l − 1 to have a perfect code, where p is a prime and p l the largest power of p dividing n . Similar results for total perfect codes are also obtained in the paper. [ABSTRACT FROM AUTHOR]

Let Γ be a distance-regular graph with valency k and diameter D , and let x be a vertex of Γ . We denote by k i ( 0 ≤ i ≤ D ) the number of vertices at distance i from x . In this paper, we try to quantify the difference between antipodal and non-antipodal distance-regular graphs. We will look at the sum k D − 1 + k D , and consider the situation where k D − 1 + k D ≤ 2 k . If Γ is an antipodal distance-regular graph, then k D − 1 + k D = k D ( k + 1 ) . It follows that either k D = 1 or the graph is non-antipodal. And for a non-antipodal distance-regular graph, it was known that k D ( k D − 1 ) ≥ k and k D − 1 ≥ k both hold. So, this paper concerns on obtaining more detailed information on the number of vertices for a non-antipodal distance-regular graph. We first concentrate on the case where the diameter equals three. In this case, the condition k D + k D − 1 ≤ 2 k is equivalent to the condition that the number of vertices is at most 3 k + 1 . And we extend this result to all diameters. We note that although the result of the diameter 3 case is a corollary of the result of all diameters, the main difficulty is the diameter 3 case, and that the diameter 3 case confirms the following conjecture: there is no primitive distance-regular graph with diameter 3 having the M -property. [ABSTRACT FROM AUTHOR]

Analogous to MacMahon’s definition of compositions, the second author, 2000, defined n -color compositions as n -color ordered partitions. Several combinatorial properties of n -color compositions were subsequently found by him, 2003, G. Narang and A.K. Agarwal, 2006, 2008, and C. Shapcott, 2012. Recently, Y. Guo 2012, 2013, studied three restricted n -color composition functions and found generating functions, explicit formulas and recurrence relations for them. In this paper, we introduce nine new restricted n -color composition functions. It is then shown that three of them are equal to three other functions. Eventually, here we study six integer sequences from the combinatorial point of view. In addition to generating functions, explicit formulas and recurrence relations for each of them, we also obtain six combinatorial identities involving different n -color composition functions. The main results of this paper are contained in Section 3. [ABSTRACT FROM AUTHOR]

In this paper we consider the existence of ( s , p )-equitable block-colorings of 4-cycle decompositions of K v − F , where F is a 1-factor of K v . In such colorings, the 4-cycles are colored with s colors in such a way that, for each vertex u , the 4-cycles containing u are colored with p colors so that the number of such 4-cycles of each color is within one of the number of such 4-cycles of each of the other p − 1 colors. Of primary interest is settling the values of χ p ′ ( v ) and χ ̄ p ′ ( v ) , namely the least and greatest values of s for which there exists such a block-coloring of some 4-cycle decomposition of K v − F . In this paper, several general results are established, both existence and non-existence theorems. These are then used to find, for all possible values of v , the values of χ p ′ ( v ) when p ∈ { 2 , 3 , 4 } and χ ̄ 2 ′ ( v ) , and to provide good upper bounds on χ ̄ 3 ′ ( v ) . [ABSTRACT FROM AUTHOR]

A Cayley graph Γ = Cay ( G , S ) is said to be core-free if G is core-free in some X ≤ Aut Γ . In this paper, a characterization of connected core-free pentavalent 1-transitive Cayley graphs is given. Moreover, the argument in this paper also gives another proof for a result in Zhou and Feng (2010) which says that all connected pentavalent 1-transitive Cayley graphs of finite non-abelian simple groups are normal. [ABSTRACT FROM AUTHOR]

Freeman’s centralization (Freeman, 1978) for a given centrality index is a measure of how central a vertex is regarding to how central all the other vertices are with respect to the given index. The transmission of a vertex v in a graph G is equal to the sum of distances between v and all other vertices of G . In this paper we study the centralization of transmission, in particular, we determine the graphs on n vertices which attain the maximum or minimum value. Roughly, the maximizing graphs are comprised of a path which has one end glued to a clique of similar order. The minimizing family of extremal graphs consists of three paths of almost the same length, glued together in one end-vertex. We conclude the paper with some problems for possible further work. [ABSTRACT FROM AUTHOR]

In Bryant et al. (1996) it is shown that there exists a 5-cycle system of K v + u − K v if and only if the obvious necessary conditions are satisfied. One purpose of this paper is to extend this result by providing the necessary and sufficient conditions for the existence of a 5-cycle system of λ K v + u − λ K v . It was shown in Asplund et al. (2013) that if there exists a 5-cycle system of λ K v , then there exists a 5-cycle system of ( λ + m ) K v + 1 − λ K v if and only if v is ( λ , 5 ) -admissible. The second purpose of this paper is to extend this result by removing the requirement that there exists a 5-cycle system of λ K v . In doing so, we will show that there exists a 5-cycle system of ( λ + m ) K v + 1 − λ K v if and only if the obvious necessary conditions are satisfied, except possibly in two cases. [ABSTRACT FROM AUTHOR]

A graph H has the hourglass property if in every induced hourglass S (the unique simple graph with the degree sequence (4, 2, 2, 2, 2)), there are two non-adjacent vertices which have a common neighbor in H-(S). Let G be a claw-free simple graph and k a positive integer. In this paper, we prove that if either G is hourglass-free or G has the hourglass property and δ(G) ≥ 4, then G has a 2-factor with at most k components if and only if it has an even factor with at most k components. We provide some of its applications: combining the result (the case when k=1) with Jaeger (1979) and Chen et al. (2006), we obtain that every 4-edge-connected claw-free graph with the hourglass property is hamiltonian and that every essentially 4-edge-connected claw-free hourglass-free graph of minimum degree at least three is hamiltonian, thereby generalizing the main result in Kaiser et al. (2005) and the result in Broersma et al. (2001) respectively in which the conditions on the vertex-connectivity are replaced by the condition of (essential) 4-edge-connectivity. Combining our result with Catlin and Lai (1990), Lai et al. (2010) and Paulraja (1987), we also obtain several other results on the existence of a hamiltonian cycle in claw-free graphs in this paper. [ABSTRACT FROM AUTHOR]

Abstract: One of the most interesting new developments in hypergraph colourings in the last few years has been Voloshin’s notion of colourings of mixed hypergraphs. In this paper we shall study a specific instance of Voloshin’s idea: a non-monochromatic non-rainbow (NMNR) colouring of a hypergraph is a colouring of its vertices such that every edge has at least two vertices coloured with different colours (non-monochromatic) and no edge has all of its vertices coloured with distinct colours (non-rainbow). Perhaps the most intriguing phenomenon of such colourings is that a hypergraph can have gaps in its NMNR spectrum, that is, for some , the hypergraph is NMNR colourable with and with colours but not with colours. Several beautiful examples have been constructed of NMNR colourings of hypergraphs exhibiting phenomena not seen in classical colourings. Many of these examples are either ad hoc or else are based on designs. The latter are difficult to construct and they generally give uniform -hypergraphs only for low values of , generally . In this paper we shall study the NMNR colourings of a type of -uniform hypergraph which we call -hypergraphs. The attractive feature of these -hypergraphs is that they are easy to define, even for large , and that, by suitable modifications of their parameters, they can give families of hypergraphs which are guaranteed to have NMNR spectra with gaps or NMNR spectra without gaps. These -hypergraphs also team up very well with the notion of colour-bounded hypergraphs recently introduced by Bujtás and Tuza to give further control on the appearance of gaps and perhaps explain better the existence of gaps in the colouring of mixed hypergraphs. [Copyright &y& Elsevier]

Abstract: Let be a map on a closed surface and suppose that each country of the map has at most disjoint connected regions. Such a map is called an -pire map on . In 1890, Heawood proved that the countries of can be properly colored with colors, where is the Euler characteristic of . Also, he conjectured that this is best possible except for the case , and now it is proved for all cases where and some cases where . We call a graph on an even embedding if it has no faces of boundary length odd. In this paper, we consider the -pire maps whose underlying graphs are even embeddings on . In my recent paper, it was proved that such a map can be properly colored with colors. In this paper, we show the best possibility of this value for some cases where . [Copyright &y& Elsevier]

Abstract: In this paper, we consider the relationship between -factors and component-deleted subgraphs of graphs. Let be a graph. A factor of is a complete-factor if every component of is complete. If is a complete-factor of , and is a component of , then is a component-deleted subgraph. Let denote the number of components of . Let be an integer-valued function defined on with even. Enomoto and Tokuda [H. Enomoto, T. Tokuda, Complete-factors and -factors, Discrete Math. 220 (2000) 239–242] proved that if is a complete-factor of with , and has an -factor for each component of , then has an -factor. We extend their result, and show that it suffices to consider a complete-factor of for some specified instead of . Let be a complete-factor of with . If has an -factor for each component of , then has an -factor in each of the following cases: (1) ; (2) is even and ; (3) has no isolated vertices and ; or (4) has no isolated vertices, is even and . We show that the results in this paper are sharp in some sense. [Copyright &y& Elsevier]

Abstract: This is fourth paper out of five in which we completely solve a problem of Dobrynin, Entringer and Gutman. Let be a graph. Denote by its -iterated line graph and denote by its Wiener index. Moreover, denote by a tree on six vertices, out of which two have degree 3 and four have degree 1. Let . In previous papers we proved that for every tree , which is not homeomorphic to a path, claw and , it holds . Here we prove that for every tree homeomorphic to . As a consequence, we obtain that with the exception of paths and the claw , for every tree it holds whenever . [Copyright &y& Elsevier]

Abstract: In a previous paper, the authors used cyclic and extended cyclic constructions to obtain codes over an alphabet {A,C,G,T} satisfying a Hamming distance constraint and a GC-content constraint. These codes are applicable to the design of synthetic DNA strands used in DNA microarrays, as DNA tags in chemical libraries and in DNA computing. The GC-content constraint specifies that a fixed number of positions are G or C in each codeword, which ensures uniform melting temperatures. The Hamming distance constraint is a step towards avoiding unwanted hybridizations. This approach extended the pioneering work of Gaborit and King. In the current paper, another constraint known as a reverse-complement constraint is added to further prevent unwanted hybridizations. Many new best codes are obtained, and are reproducible from the information presented here. The reverse-complement constraint is handled by searching for an involution with 0 or 1 fixed points, as first done by Gaborit and King. Linear codes and additive codes over GF(4) and their cosets are considered, as well as shortenings of these codes. In the additive case, codes obtained from two different mappings from GF(4) to {A,C,G,T} are considered. [Copyright &y& Elsevier]

Abstract The combinatorial object named t -spontaneous emission error design (t -SEED) was proposed by Beth et al. in 2003 in order to correct errors caused by quantum jumps. The newly rising category of t -SEEDs has been studied extensively in recent years. Especially, the maximal possible dimensions for 2-SEEDs with block size 3 were determined completely; lower bounds on 2-SEEDs were established by applying affine groups. In this paper we utilize the action of twisted affine groups on finite fields and obtain new lower bounds on the dimensions of 2- (q 2 , k ; m) SEEDs, some of which outperform the known ones. [ABSTRACT FROM AUTHOR]

Abstract Let G be an additive finite abelian group with exponent exp (G) = n. For any positive integer k , the k th Erdős–Ginzburg–Ziv constant s k n (G) is defined as the smallest positive integer t such that every sequence S in G of length at least t has a zero-sum subsequence of length k n. It is easy to see that s k n (C n r) ≥ (k + r) n − r where n , r ∈ N. Kubertin conjectured that the equality holds for any k ≥ r. In this paper, we prove the following results: • [(1)] For every positive integer k ≥ 6 , we have s k n (C n 3) = (k + 3) n + O (n ln n). • [(2)] For every positive integer k ≥ 18 , we have s k n (C n 4) = (k + 4) n + O (n ln n). • [(3)] For n ∈ N , assume that the largest prime power divisor of n is p a for some a ∈ N. Forany fixed r ≥ 5 , if p t ≥ r for some t ∈ N , then for any k ∈ N we have s k p t n (C n r) ≤ (k p t + r) n + c r n ln n , where c r is a constant that depends on r. Our results verify the conjecture of Kubertin asymptotically in the above cases. [ABSTRACT FROM AUTHOR]

Abstract In this paper a relationship is established between the domination game and minimal edge cuts. It is proved that the game domination number of a connected graph can be bounded above in terms of the size of minimal edge cuts. In particular, if C a minimum edge cut of a connected graph G , then γ g (G) ≤ γ g (G ∖ C) + 2 κ ′ (G). Double-Staller graphs are introduced in order to show that this upper bound can be attained for graphs with a bridge. The obtained results are used to extend the family of known traceable graphs whose game domination numbers are at most one-half their order. Along the way two technical lemmas, which seem to be generally applicable for the study of the domination game, are proved. [ABSTRACT FROM AUTHOR]

Abstract Kreweras conjectured that every perfect matching of a hypercube Q n for n ≥ 2 can be extended to a hamiltonian cycle of Q n. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of Q n for n ≥ 2 can be extended to two or more hamiltonian cycles of Q n. In this paper, we prove that every perfect matching of Q n for n ≥ 4 can be extended to at least 2 2 n − 4 different hamiltonian cycles of Q n. [ABSTRACT FROM AUTHOR]

Abstract Let G be a bridgeless cubic graph. Oddness (weak oddness) is defined as the minimum number of odd components in a 2-factor (an even factor) of G , denoted as ω (G) (Steffen, 2004) (ω ′ (G) Lukot'ka and Mazák (2016)). Oddness and weak oddness have been referred to as measurements of uncolourability (Fiol et al., 2017, Lukot'ka and Mazák, 2016, Lukot'ka et al., 2015 and, Steffen, 2004), due to the fact that ω (G) = 0 and ω ′ (G) = 0 if and only if G is 3-edge-colourable. Another so-called measurement of uncolourability is resistance, defined as the minimum number of edges that can be removed from G such that the resulting graph is 3-edge-colourable, denoted as r (G) (Steffen, 2004). It is easily shown that ω (G) ≥ ω ′ (G) ≥ r (G). While it has been shown that the difference between any two of these measures can be arbitrarily large, it has been conjectured that ω ′ (G) ≤ 2 r (G) , and that if G is a snark then ω (G) ≤ 2 r (G) (Fiol et al., 2017). In this paper, we disprove the latter by showing that the ratio of oddness to weak oddness can be arbitrarily large. We also offer some insights into the former conjecture by defining what we call resistance reducibility , and hypothesizing that almost all cubic graphs are such resistance reducible. [ABSTRACT FROM AUTHOR]

Abstract Given two graphs G and H , the rainbow number r b (G , H) for H with respect to G is defined as the minimum number k such that any k -edge-coloring of G contains a rainbow H , i.e., a copy of H , all of whose edges have different colors. Denote by k K 2 a matching of size k and T n the class of all plane triangulations of order n , respectively. In Jendrol ′ et al. (2014), the authors determined the exact values of r b (T n , k K 2) for 2 ≤ k ≤ 4 and proved that 2 n + 2 k − 9 ≤ r b (T n , k K 2) ≤ 2 n + 2 k − 7 + 2 2 k − 2 3 for k ≥ 5. In this paper, we improve the upper bounds and prove that r b (T n , k K 2) ≤ 2 n + 6 k − 16 for n ≥ 2 k and k ≥ 5. Especially, we show that r b (T n , 5 K 2) = 2 n + 1 for n ≥ 11. [ABSTRACT FROM AUTHOR]

Abstract A Weyl arrangement is the hyperplane arrangement defined by a root system. Saito proved that every Weyl arrangement is free. The Weyl subarrangements of type A ℓ are represented by simple graphs. Stanley gave a characterization of freeness for this type of arrangements in terms of their graph. In addition, the Weyl subarrangements of type B ℓ can be represented by signed graphs. A characterization of freeness for them is not known. However, characterizations of freeness for a few restricted classes are known. For instance, Edelman and Reiner characterized the freeness of the arrangements between type A ℓ − 1 and type B ℓ. In this paper, we give a characterization of the freeness and supersolvability of the Weyl subarrangements of type B ℓ under certain assumption. [ABSTRACT FROM AUTHOR]

Abstract: There have been several papers on the subject of traditional peg solitaire on different boards. However, in this paper we consider a generalization of the game to arbitrary boards. These boards are treated as graphs in the combinatorial sense. We present necessary and sufficient conditions for the solvability of several well-known families of graphs. In the major result of this paper, we show that the cartesian product of two solvable graphs is likewise solvable. Several related results are also presented. Finally, several open problems related to this study are given. [Copyright &y& Elsevier]

Abstract: A graph of order is called degree-equipartite if for every -element set , the degree sequences of the induced subgraphs and are the same. In this paper, we characterize all degree-equipartite graphs. This answers Problem 1 in the paper by Grünbaum et al. [B. Grünbaum, T. Kaiser, D. Král, and M. Rosenfeld, Equipartite graphs, Israel J. Math. 168 (2008) 431–444]. [Copyright &y& Elsevier]

Abstract: In this paper, we define the path relation of a directed graph to be the relation which relates two vertices if there is a path from the first to the second. We study the restriction of this relation to paths from sources to sinks, and consider the question of when two finite graphs embedded in a rectangle give the same relation. We find a set of local changes to these graphs which can be used to get between any two graphs for which this relation is the same. Furthermore, we classify the relations which can arise as this relation for a finite directed graph embedded in a rectangle as the triconvex relations between finite ordinals (defined in this paper). This work originated from some of the author’s work on category theory. It turns out that the category of finite ordinals and relations that can be the path relation of a directed graph embedded in a rectangle, is relevant to the study of diads—introduced by the author as a common generalisation of monads and comonads (note that the terms diad and dyad have been used to mean different things by other authors). More specifically, the referee of one of the author’s papers suggested that it would be useful to identify the category which plays the role for diads that the category of finite ordinals and order-preserving functions plays for monads. It turns out that the category of finite ordinals and relations that can be path relations of graphs embedded in a rectangle, is exactly the category that plays this role. [ABSTRACT FROM AUTHOR]

Abstract: Vector space partitions of an -dimensional vector space over a finite field are considered in Bu (1980) , Heden (1984) , and more recently in a series of papers Blinco et al. (2008) , El-Zanati et al. (2008, 2009) . In this paper, we consider the generalization of a vector space partition which we call a -fold partition (or simply a -partition). In particular, for a given positive integer, , we define a -fold partition of to be a multiset of subspaces of such that every nonzero vector in is contained in exactly subspaces in the given multiset. A -fold spread as defined in Hirschfeld (1998) is one example of a -fold partition. After establishing some definitions in the introduction, we state some necessary conditions for a -fold partition of to exist, then introduce some general ways to construct such partitions. We also introduce the construction of a dual -partition as a way of generating -partitions from a given -partition. One application of this construction is that the dual of a vector space partition will, in general, be a -partition for some . In the last section, we discuss a connection between -partitions and some designs over finite fields. [Copyright &y& Elsevier]

Abstract: Došlić and Måløy (2010) obtained the extremal 6-cactus chains with respect to the number of matchings and of independent sets. Motivated by the prior paper, in this paper we give recurrences for matching polynomials of ortho-chains and meta-chains, and show that they are the -cactus chains with the most matchings. [Copyright &y& Elsevier]

Abstract: The linear discrepancy of a poset is the least such that there is a linear extension of such that if and are incomparable, then , whereas the weak discrepancy is the least such that there is a weak extension of such that if and are incomparable, then . This paper resolves a question of Tanenbaum, Trenk, and Fishburn on characterizing when the weak and linear discrepancy of a poset are equal. Although it is shown that determining whether a poset has equal weak and linear discrepancy is -complete, this paper provides a complete characterization of the minimal posets with equal weak and linear discrepancy. Further, these minimal posets can be completely described as a family of interval orders. [Copyright &y& Elsevier]

Abstract In 2012, Lin (Electron. J. Combin. 19(2) (2012) #P17) investigated the 2 and 3-divisibility properties for p p ¯ o (n) , the number of overpartition pairs into odd parts. Using modular forms, he proved that for a fixed positive integer k , p p ¯ o (n) is almost always divisible by 2 k. In this paper, we prove several congruences for p p ¯ o (n) modulo higher powers of 2 in an elementary way. [ABSTRACT FROM AUTHOR]

A graph is equimatchable if all of its maximal matchings have the same size. A graph is claw-free if it does not have a claw as an induced subgraph. In this paper, we provide the first characterization of claw-free equimatchable graphs by identifying the equimatchable claw-free graph families. This characterization implies an efficient recognition algorithm. [ABSTRACT FROM AUTHOR]

Abstract: For three types of triples, unordered, cyclic and transitive, the corresponding extended triple, extended triple system and their large set are introduced. The spectrum of for even has been given in our paper (Liu and Kang (2009) ). In this paper, we shall discuss the existence problem of for odd and give the almost complete conclusion: there exists an for any positive integer except possible . [ABSTRACT FROM AUTHOR]

Abstract: In a recent paper, Hladký et al. (2009) (see ) proved that for , any digraph of order with minimum out-degree at least contains a cycle of length at most 3. Hamburger et al. (2007) (see ) proved that for , any digraph of order with both minimum out-degree and minimum in-degree at least contains a cycle of length at most . In this paper, by using the first result, we slightly improve the second bound. Namely, we prove that for , any digraph of order with both minimum out-degree and minimum in-degree at least contains a cycle of length at most 3. This result will be in fact a consequence of a quite general result. [ABSTRACT FROM AUTHOR]

Abstract: This paper discusses an attempt at identifying a property of circuits in (nonplanar) graphs resembling the separation property of circuits in planar graphs derived from the Jordan Curve Theorem. If is a graph and is a circuit in , we say that two circuits in form a split of if the symmetric difference of their edges sets is equal to the edge set of , and if they are separated in by the intersection of their vertex sets. García Moreno and Jensen, A note on semiextensions of stable circuits, Discrete Math. 309 (2009) 4952–4954, asked whether such a split exists for any circuit whenever is 3-connected. We observe that if true, this implies a strong form of a version of the Cycle Double-Cover Conjecture suggested in the Ph.D. thesis of Luis Goddyn. The main result of the paper shows that the property holds for Hamilton circuits in cubic graphs. [ABSTRACT FROM AUTHOR]

Abstract: A graph is said to have property if it contains a perfect matching and for every pair of disjoint matchings and in with and , there is a perfect matching in such that and . In a previous paper (Aldred and Plummer 2001) , an investigation of the property was begun for graphs embedded in the plane. In particular, although no planar graph is , it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, denotes a loopless directed graph (digraph) with at most one arc from to for every pair of vertices and of . Given a digraph , we say that is 3-quasi-transitive if, whenever in , then and are adjacent or . In Bang-Jensen (2004) , Bang-Jensen introduced 3-quasi-transitive digraphs and claimed that the only strong 3-quasi-transitive digraphs are the strong semicomplete digraphs and strong semicomplete bipartite digraphs. In this paper, we exhibit a family of strong 3-quasi-transitive digraphs distinct from strong semicomplete digraphs and strong semicomplete bipartite digraphs and provide a complete characterization of strong 3-quasi-transitive digraphs. [Copyright &y& Elsevier]

Abstract: In a recent paper, Bessy, Sereni and the author (see ) have proved that for , a tournament with minimum out-degree and in-degree both greater than or equal to contains at least vertex-disjoint directed triangles. In this paper, we generalize this result; more precisely, we prove that for given integers and , a tournament with minimum out-degree and in-degree both greater than or equal to contains at least vertex-disjoint directed cycles of length . We will use an auxiliary result established in , concerning a union of sets contained in another union of sets. We finish by giving a lower bound on the maximum number of vertex-disjoint directed cycles of length when only the minimum out-degree is supposed to be greater than or equal to . [Copyright &y& Elsevier]

Abstract: Let be a poset in which each point is incomparable to at most others. Tanenbaum, Trenk, and Fishburn asked in a 2001 paper if the linear discrepancy of such a poset is bounded above by . This paper answers their question in the affirmative for two classes of posets. The first class is the interval orders, which are shown to have linear discrepancy at most , with equality precisely for interval orders containing an antichain of size . The stronger bound is tight even for interval orders of width 2. The second class of posets considered is the disconnected posets, which have linear discrepancy at most . This paper also contains lemmas on the role of critical pairs in linear discrepancy as well as a theorem establishing that every poset contains a point whose removal decreases the linear discrepancy by at most 1. [Copyright &y& Elsevier]

Abstract: A digraph without loops, multiple arcs and directed cycles of length two is called a local tournament if the set of in-neighbors as well as the set of out-neighbors of every vertex induces a tournament. In this paper we consider the following problem: Given a strongly connected local tournament of order and an integer , how many directed cycles of length exist in ? Bang-Jensen  showed in 1990 that every strongly connected local tournament has a directed Hamiltonian cycle, thus solving the case . In 2009, Meierling and Volkmann  showed that a strongly connected local tournament has at least directed cycles of length for unless it has a special structure. In this paper, we investigate the case and present a lower bound for the number of directed cycles of length three. Furthermore, we characterize the classes of local tournaments achieving equality in the bounds for and , respectively. [Copyright &y& Elsevier]

Abstract: For three types of triples: unordered, cyclic and transitive, the corresponding extended triple, extended triple system and their large sets are introduced. The existence of and were completely solved. In this paper, we shall discuss the existence problem of and give the following conclusion: there exists an for any even except . The existence of with odd order will be discussed in another paper, we are working at it. [Copyright &y& Elsevier]

Abstract: We consider finite analogues of Euclidean graphs in a more general setting than that considered in [A. Medrano, P. Myers, H.M. Stark, A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math. 68 (1996) 221–238] and we obtain many new examples of Ramanujan graphs. In order to prove these results, we use the previous work of [W.M. Kwok, Character tables of association schemes of affine type, European J. Combin. 13 (1992) 167–185] calculating the character tables of certain association schemes of affine type. A key observation is that we can obtain better estimates for the ordinary Kloosterman sum . In particular, we always achieve , and in many (but not all) of the cases, instead of the well known . Also, we use the ideas of controlling association schemes, and the Ennola type dualities, in our previous work on the character tables of commutative association schemes. The method in this paper will be used to construct many more new examples of families of Ramanujan graphs in the subsequent paper. [Copyright &y& Elsevier]

Abstract: The Strong Perfect Graph Conjecture (SPGC) was certainly one of the most challenging conjectures in graph theory. During more than four decades, numerous attempts were made to solve it, by combinatorial methods, by linear algebraic methods, or by polyhedral methods. The first of these three approaches yielded the first (and to date only) proof of the SPGC; the other two remain promising to consider in attempting an alternative proof. This paper is an unbalanced survey of the attempts to solve the SPGC; unbalanced, because (1) we devote a significant part of it to the ‘primitive graphs and structural faults’ paradigm which led to the Strong Perfect Graph Theorem (SPGT); (2) we briefly present the other “direct” attempts, that is, those for which results exist showing one (possible) way to the proof; (3) we ignore entirely the “indirect” approaches whose aim was to get more information about the properties and structure of perfect graphs, without a direct impact on the SPGC. Our aim in this paper is to trace the path that led to the proof of the SPGT as completely as possible. Of course, this implies large overlaps with the recent book on perfect graphs [J.L. Ramirez-Alfonsin, B.A. Reed (Eds.), Perfect Graphs, Wiley & Sons, 2001], but it also implies a deeper analysis (with additional results) and another viewpoint on the topic. [Copyright &y& Elsevier]

Abstract: This paper gives a characterization of connected cubic -transitive Cayley graphs. It is shown that, for , every connected cubic -transitive Cayley graph is a normal cover of one of 13 graphs: three 3-transitive graphs, four 4-transitive graphs and six 5-transitive graphs. Moreover, the argument in this paper also gives another proof for a well-known result which says that all connected cubic arc-transitive Cayley graphs of finite non-abelian simple groups are normal except two 5-transitive Cayley graphs of the alternating group . [Copyright &y& Elsevier]

Abstract: A central question in design theory dating from Kirkman in 1850 has been the existence of resolvable block designs. In this paper we will concentrate on the case when the block size . The necessary condition for a resolvable design to exist when is that ; this was proven sufficient in 1972 by Hanani, Ray-Chaudhuri and Wilson [H. Hanani, D.K. Ray-Chaudhuri, R.M. Wilson, On resolvable designs, Discrete Math. 3 (1972) 343–357]. A resolvable pairwise balanced design with each parallel class consisting of blocks which are all of the same size is called a uniformly resolvable design, a URD. The necessary condition for the existence of a URD with block sizes 2 and 4 is that . Obviously in a URD with blocks of size 2 and 4 one wishes to have the maximum number of resolution classes of blocks of size 4; these designs are called maximum uniformly resolvable designs or MURDs. So the question of the existence of a MURD on points has been solved for by the result of Hanani, Ray-Chaudhuri and Wilson cited above. In the case this problem has essentially been solved with a handful of exceptions (see [G. Ge, A.C.H. Ling, Asymptotic results on the existence of 4-RGDDs and uniform 5-GDDs, J. Combin. Des. 13 (2005) 222–237]). In this paper we consider the case when and prove that a exists for all with the possible exception of . [Copyright &y& Elsevier]

Abstract: A cyclic edge-cut of a graph is an edge set, the removal of which separates two cycles. If has a cyclic edge-cut, then it is said to be cyclically separable. For a cyclically separable graph , the cyclic edge-connectivity is the cardinality of a minimum cyclic edge-cut of . In this paper, we first prove that for any cyclically separable graph , , where is the number of edges with one end in and the other end in . A cyclically separable graph with is said to be cyclically optimal. The main results in this paper are: any connected -regular vertex-transitive graph with and girth at least 5 is cyclically optimal; any connected edge-transitive graph with minimum degree at least 4 and order at least 6 is cyclically optimal. [Copyright &y& Elsevier]

Abstract: A tree is a chemical tree if its maximum degree is at most 4. Hansen and Mélot [P. Hansen, H. Mélot, Variable neighborhood search for extremal graphs 6: analyzing bounds for the connectivity index, J. Chem. Inf. Comput. Sci. 43 (2003) 1–14], Li and Shi [X. Li, Y.T. Shi, Corrections of proofs for Hansen and Mélot’s two theorems, Discrete Appl. Math., 155 (2007) 2365–2370] investigated extremal Randić indices of the chemical trees of order with pendants. In their papers, they obtained that an upper bound for Randić index is . This upper bound is sharp for but not for . In this paper, we find the maximum Randić index for . Examples of chemical trees corresponding to the maximum Randić indices are also constructed. [Copyright &y& Elsevier]

Abstract: Let be a graph, and let and be nonnegative integers with . An -factor of graph is defined as a spanning subgraph of such that for each . Then a graph is called an -critical graph if after deleting any vertices of the remaining graph of has an -factor. In this paper, it is proved that if , then is an -critical graph. Furthermore, it is showed that the result in this paper is best possible in some sense. [Copyright &y& Elsevier]

Abstract: A graph is a -leaf power if there is a tree such that the vertices of are the leaves of and two vertices are adjacent in if and only if their distance in is at most . In this situation is called a -leaf root of . Motivated by the search for underlying phylogenetic trees, the notion of a -leaf power was introduced and studied by Nishimura, Ragde and Thilikos and subsequently in various other papers. While the structure of 3- and 4-leaf powers is well understood, for the characterization of -leaf powers remains a challenging open problem. In the present paper, we give a forbidden induced subgraph characterization of distance-hereditary 5-leaf powers. Our result generalizes known characterization results on 3-leaf powers since these are distance-hereditary 5-leaf powers. [Copyright &y& Elsevier]

Abstract: The concept of good large set of Steiner triple systems (or GLS in short) was introduced by Lu in his paper “on large sets of disjoint Steiner triple systems”, [J. Lu, On large sets of disjoint Steiner triple systems, I–III, J. Combin. Theory (A) 34 (1983) 140-182]. In this paper a doubling construction for GLSs is displayed and some existence results are obtained. [Copyright &y& Elsevier]

Abstract: In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with , the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when is even and , the genus of when for and , and the genus of when for and . In all of these cases the genus is the same as the genus of , namely . [Copyright &y& Elsevier]

Abstract: Let be an integer and a bipartite graph with such that . In this paper it has been proved that if for each pair of nonadjacent vertices and , , then for any independent edges of , has a 2-factor with cycles such that and for each . We shall also show that the conditions in this paper are sharp. [Copyright &y& Elsevier]

Abstract: This paper investigates a competitive version of the coloring game on a finite graph . An asymmetric variant of the -relaxed coloring game is called the -relaxed -coloring game. In this game, two players, Alice and Bob, take turns coloring the vertices of a graph , using colors from a set , with . On each turn Alice colors vertices and Bob colors vertices. A color is legal for an uncolored vertex if by coloring with color , the subgraph induced by all the vertices colored with has maximum degree at most . Each player is required to color an uncolored vertex legally on each move. The game ends when there are no remaining uncolored vertices. Alice wins the game if all vertices of the graph are legally colored, Bob wins if at a certain stage there exists an uncolored vertex without a legal color. The -relaxed -game chromatic number, denoted by , of is the least for which Alice has a winning strategy in the -relaxed -coloring game. The -relaxed -coloring game has been well studied and there are many interesting results. For the -relaxed -coloring game, this paper proves that if a graph has an orientation with maximum outdegree and , then for all ; If , then - for all . [Copyright &y& Elsevier]