Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Meysam Alishahi, Hossein Hajiabolhassan For a graph G and a family of graphs F , the general Kneser graph KG ( G , F ) is a graph with the vertex set consisting of all subgraphs of G isomorphic to some member of F and two vertices are adjacent if their corresponding subgraphs are edge disjoint. In this paper, we introduce some generalizations of Turán number of graphs. In view of these generalizations, we give some lower and upper bounds for the chromatic number of general Kneser graphs KG ( G , F ) . Using these bounds, we determine the chromatic number of some family of general Kneser graphs KG ( G , F ) in terms of generalized Turán number of graphs. In particular, we determine the chromatic number of every Kneser multigraph KG ( G , F ) where G is a multigraph each of whose edges has the multiplicity at least 2 and F is an arbitrary family of simple graphs. Moreover, the chromatic number of general Kneser graph KG ( G , F ) is exactly determined where G is a dense graph and F = { K 1 , 2 } .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Pedro J. Miana, Hideyuki Ohtsuka, Natalia Romero In this paper, we consider combinatorial numbers ( C m , k ) m ≥ 1 , k ≥ 0 , mentioned as Catalan triangle numbers where C m , k ≔ m − 1 k − m − 1 k − 1 . These numbers unify the entries of the Catalan triangles B n , k and A n , k for appropriate values of parameters m and k , i.e., B n , k = C 2 n , n − k and A n , k = C 2 n + 1 , n + 1 − k . In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers C n that is C 2 n , n − 1 = C 2 n + 1 , n = C n . We present identities for sums (and alternating sums) of C m , k , squares and cubes of C m , k and, consequently, for B n , k and A n , k . In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ( C m , k ) m ≥ 1 , k ≥ 0 and harmonic numbers ( H n ) n ≥ 1 . Finally, in the last section, new open problems and identities involving ( C n ) n ≥ 0 are conjectured.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Song-Tao Guo, Hailong Hou, Yong Xu A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order 9 p for each prime p .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Boštjan Brešar A long-standing Vizing’s conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of Clark and Suen, γ ( G □ H ) ≥ γ ( G ) γ ( H ) ∕ 2 , where γ stands for the domination number, and G □ H is the Cartesian product of graphs G and H . In this note, we improve this bound by employing the 2-packing number ρ ( G ) of a graph G into the formula, asserting that γ ( G □ H ) ≥ ( 2 γ ( G ) − ρ ( G ) ) γ ( H ) ∕ 3 . The resulting bound is better than that of Clark and Suen whenever G is a graph with ρ ( G ) < γ ( G ) ∕ 2 , and in the case G has diameter 2 reads as γ ( G □ H ) ≥ ( 2 γ ( G ) − 1 ) γ ( H ) ∕ 3 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Jakub Przybyło Consider a positive integer r and a graph G = ( V , E ) with maximum degree Δ and without isolated edges. The least k so that a proper edge colouring c : E → { 1 , 2 , … , k } exists such that ∑ e ∋ u c ( e ) ≠ ∑ e ∋ v c ( e ) for every pair of distinct vertices u , v at distance at most r in G is denoted by χ Σ , r ′ ( G ) . For r = 1 , it has been proved that χ Σ , 1 ′ ( G ) = ( 1 + o ( 1 ) ) Δ . For any r ≥ 2 in turn an infinite family of graphs is known with χ Σ , r ′ ( G ) = Ω ( Δ r − 1 ) . We prove that, on the other hand, χ Σ , r ′ ( G ) = O ( Δ r − 1 ) for r ≥ 2 . In particular, we show that χ Σ , r ′ ( G ) ≤ 6 Δ r − 1 if r ≥ 4 .

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Jiuqiang Liu, Xiaodong Liu In this paper, we derive a best possible k -wise extension to the well-known Snevily theorem on set systems (Snevily, 2003) which strengthens the well-known theorem by Füredi and Sudakov (2004). We also provide a conjecture which gives a common generalization to all existing non-modular L -intersection theorems.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Shangwei Lin, Ya’nan Jin, Chunfang Li The k -restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset S of a strong digraph D is a k -restricted arc cut if D − S has a strong component D ′ with order at least k such that D − V ( D ′ ) contains a connected subdigraph with order at least k . The k -restricted arc connectivity λ k ( D ) of a digraph D is the minimum cardinality over all k -restricted arc cuts of D . Let D be a strong digraph with order n ≥ 6 and minimum degree δ ( D ) . In this paper, we first show that λ 3 ( D ) exists if δ ( D ) ≥ 3 and, furthermore, λ 3 ( D ) ≤ ξ 3 ( D ) if δ ( D ) ≥ 4 , where ξ 3 ( D ) is the minimum 3-degree of D . Next, we prove that λ 3 ( D ) = ξ 3 ( D ) if δ ( D ) ≥ n + 3 2 . Finally, we give examples showing that these results are best possible in some sense.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Michael A. Henning, Anders Yeo A transversal in a hypergraph H is a subset of vertices that has a nonempty intersection with every edge of H . A transversal family F of H is a family of (not necessarily distinct) transversals of H . The effective transversal-ratio of the family F is the ratio of the number of sets in F over the maximum times r F any element appears in F . The fractional disjoint transversal number FDT ( H ) is the supremum of the effective transversal-ratio taken over all transversal families. That is, FDT ( H ) = sup F F ∕ r F . Using a connection with not-all-equal 3 -SAT, we prove that if H is a 3 -regular 3 -uniform hypergraph, then FDT ( H ) ≥ 2 , which proves a known conjecture. Using probabilistic arguments, we prove that for all k ≥ 3 , if H is a k -regular k -uniform hypergraph, then FDT ( H ) ≥ 1 ∕ ( 1 − ( k − 1 k ) 1 k 1 k − 1 ) , and that this bound is essentially best possible.

Abstract: Publication date: October 2017 Source:Discrete Mathematics, Volume 340, Issue 10 Author(s): Artem Napov We establish a divide-and-conquer bound for the aggregate’s quality and algebraic connectivity measures, as defined for weighted undirected graphs. Aggregate’s quality is defined on a set of vertices and, in the context of aggregation-based multigrid methods, it measures how well this set of vertices is represented by a single vertex. On the other hand, algebraic connectivity is defined on a graph, and measures how well this graph is connected. The considered divide-and-conquer bound for aggregate’s quality relates the aggregate’s quality of a union of two disjoint sets of vertices to the aggregate’s quality of the two sets. Likewise, the bound for algebraic connectivity relates the algebraic connectivity of the graph induced by a union of two disjoint sets of vertices to the algebraic connectivity of the graphs induced by the two sets.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Peter Borg A set of sets is called a family. Two families A and B are said to be cross- t -intersecting if each set in A intersects each set in B in at least t elements. For a family F , let l ( F , t ) denote the size of a largest subfamily of F whose sets have at least t common elements. We call F a ( ≤ r ) -family if each set in F has at most r elements. We show that for any positive integers r , s and t , there exists an integer c ( r , s , t ) such that the following holds. If A is a subfamily of a ( ≤ r ) -family F with l ( F , t ) ≥ c ( r , s , t ) l ( F , t + 1 ) , B is a subfamily of a ( ≤ s ) -family G with l ( G , t ) ≥ c ( r , s , t ) l ( G , t + 1 ) , and A and B are cross- t -intersecting, then A B ≤ l ( F , t ) l ( G , t ) . We give c ( r , s , t ) explicitly. Some known results follow from this, and we identify several natural classes of families for which the bound is attained.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Li Liu, Lanqiang Li, Liqi Wang, Shixin Zhu In this paper, we explicitly determine the generator polynomials of all repeated-root constacyclic codes of length n l p s over F q and their dual codes, where l is an odd prime different from p , and n is an odd prime different from both l and p such that n = 2 h + 1 for some prime h or h = 1 . Moreover, we give all self-dual cyclic codes of length n l p s over F q and their enumeration. All linear complementary dual (LCD) cyclic codes of length n l p s over F q and their enumeration are also obtained.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Hengjia Wei, Gennian Ge A uniformly resolvable design (URD) is a resolvable design in which each parallel class contains blocks of only one block size k . Such a class is denoted k -pc and for a given k the number of k -pcs is denoted r k . The number of points of the URD is denoted by v . In the literature, the existence of URDs of block sizes k 1 and k 2 with { k 1 , k 2 } ∈ { { 2 , 3 } , { 2 , 4 } , { 3 , 4 } } has been studied with much efforts. For { k 1 , k 2 } = { 2 , 3 } or { 3 , 4 } , the existence spectra have been determined completely, while for { k 1 , k 2 } = { 2 , 4 } there are still 1338 undetermined pairs of ( v , r 2 ) . In this paper we continue the study on the existence of URDs of block sizes 2 and 4. We improve the known results by reducing the number of open cases from 1338 to 16 . In addition, we prove that there exist 4 -RGDDs of types 2178, 2250 and 2334.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Gaojun Luo, Xiwang Cao Linear codes with few weights have applications in secret sharing, authentication codes, association schemes, data storage systems, strongly regular graphs and some other fields. Two-weight linear codes are particularly interesting since they are closely related to finite geometry, combinatorial designs, graph theory. In this paper, we present a new approach to constructing linear codes with two or three weights from q -polynomials and study their weight distributions. As an application of two-weight linear codes, we obtain three families of strongly regular graphs. Some of the presented strongly regular graphs are new.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): F. Botler, A. Talon A T -decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G . Graham and Häggkvist (1989) conjectured that any 2 ℓ -regular graph G admits a T -decomposition if T is a tree with ℓ edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with ℓ edges, G admits a T -decomposition D where every vertex of G is the end-vertex of exactly two paths of D , and proved that this statement holds when G has girth at least ( ℓ + 3 ) ∕ 2 . In this paper we verify Kouider and Lonc’s Conjecture for paths of length 4 .

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Gérard H.E. Duchamp, Jean-Yves Enjalbert, Vincel Hoang Ngoc Minh, Christophe Tollu Nous poursuivons ici le travail commencé dans (Enjalbert and Hoang Ngoc Minh, 2012) en décrivant des produits de mélanges d’algèbres de plus en plus “grandes” de fonctions spéciales (issues d’équations différentielles à pôles simples). Les étudier nous conduit à définir une classe de produits de mélange, que nous nommons φ -shuffles. Nous étudions cette classe d’un point de vue combinatoire, en commençant par étendre (sous conditions) le théorème de Radford à celle-ci, puis en construisant (toujours sous conditions) sa bigèbre. Nous analysons les conditions des résultats précités pour les simplifier en les rendant visible dès la définition du produit de mélange. Nous testons enfin ces conditions sur les produits introduits en début d’article. We carry on the investigation initiated in Enjalbert and Hoang Ngoc Minh (2012): we describe new shuffle products coming from some special functions and group them, along with other products encountered in the literature, in larger and larger classes of products, which we name φ -shuffle products. Our paper is dedicated to a study of the latter class, from a combinatorial standpoint. We consider first how to extend Radford’s theorem to the products in that class, then how to construct their bi-algebras. As some conditions are necessary to carry that out, we study them closely and simplify them so that they can be seen directly from the definition of the product. We eventually test these conditions on the products mentioned above.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Robert E. Jamison, Henry Martyn Mulder A graph G is Θ 3 -closed provided any two vertices of G that are joined by three internally disjoint paths are adjacent. We show that the Θ 3 -closed graphs are precisely those that can be obtained by gluing together cliques and cycles along vertices or edges.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Jiangmin Pan, Bo Ling, Suyun Ding A graph is called symmetric if its automorphism group is transitive on its arcs. In this paper, we classify symmetric graphs of order four times an odd square-free integer and valency seven. It is shown that, either the graph is isomorphic to one of 9 specific graphs or its full automorphism group is isomorphic to PSL ( 2 , p ) , PGL ( 2 , p ) , PSL ( 2 , p ) × Z 2 or PGL ( 2 , p ) × Z 2 with p ≡ ± 1 ( mod 7 ) a prime.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): João Carvalho, Bruna S. Souza, Vilmar Trevisan, Fernando C. Tura We develop an algorithm for computing the characteristic polynomial of matrices related to threshold graphs. We use this as tool to exhibit, for any natural number n ≥ 4 , 2 n − 4 graphs with n vertices that have a non isomorphic pair with the same signless Laplacian spectrum. We also show how to construct infinite families of pairs of non isomorphic graphs having the same Q -spectrum.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): M.H. Shirdareh Haghighi, F. Motialah, B. Amini A graph G of order 2 n is called equipartite if for every n -element set A ⊆ V ( G ) , there exists an automorphism of G that maps the induced subgraph G [ A ] onto G [ V ( G ) ∖ A ] . In this paper, we show that a graph G of order 2 n is equipartite if and only if for every such partition of V ( G ) , the induced subgraphs G [ A ] and G [ V ( G ) ∖ A ] have the same Laplacian spectra.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Sen-Peng Eu, Seunghyun Seo, Heesung Shin In this paper we enumerate and give bijections for the following four sets of vertices among rooted ordered trees of a fixed size: (i) first-children of degree k at level ℓ , (ii) non-first-children of degree k at level ℓ − 1 , (iii) leaves having k − 1 elder siblings at level ℓ , and (iv) non-leaves of outdegree k at level ℓ − 1 . Our results unite and generalize several previous works in the literature.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Lifeng Dai, Yingqian Wang, Jinghan Xu Let d 1 , d 2 , … , d k be k non-negative integers. A graph G is ( d 1 , d 2 , … , d k ) -colorable, if the vertex set of G can be partitioned into subsets V 1 , V 2 , … , V k such that the subgraph G [ V i ] induced by V i has maximum degree at most d i for i = 1 , 2 , … , k . In this paper, we prove that every planar graph without cycles of length 4 or 9 is ( 1 , 1 , 0 ) -colorable.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Fabrício S. Benevides, Carlos Hoppen, Rudini M. Sampaio Given a graph F and an integer r ≥ 2 , a partition F ̂ of the edge set of F into at most r classes, and a graph G , define c r , F ̂ ( G ) as the number of r -colorings of the edges of G that do not contain a copy of F such that the edge partition induced by the coloring is isomorphic to the one of F . We think of F ̂ as the pattern of coloring that should be avoided. The main question is, for a large enough n , to find the (extremal) graph G on n vertices which maximizes c r , F ̂ ( G ) . This problem generalizes a question of Erdős and Rothschild, who originally asked about the number of colorings not containing a monochromatic clique (which is equivalent to the case where F is a clique and the partition F ̂ contains a single class). We use Hölder’s Inequality together with Zykov’s Symmetrization to prove that, for any r ≥ 2 , k ≥ 3 and any pattern K k ̂ of the clique K k , there exists a complete multipartite graph that is extremal. Furthermore, if the pattern K k ̂ has at least two classes, with the possible exception of two very small patterns (on three or four vertices), every extremal graph must be a complete multipartite graph. In the case that r = 3 and F ̂ is a rainbow triangle (that is, where F = K 3 and each part is a singleton), we show that an extremal graph must be an almost complete graph. Still for r = 3 , we extend a result about monochromatic patterns of Alon, Balogh, Keevash and Sudakov to some patterns that use two of the three colors, finding the exact extremal graph. For the later two results, we use the Regularity and Stability Method.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Stefaan De Winter, Eric Neubert, Zeying Wang In this note we prove the non-existence of two types of partial difference sets in Abelian groups of order 216 . This completes the classification of parameters for which a partial difference set of size at most 100 exists in an Abelian group.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Fenix W.D. Huang, Christian M. Reidys In this paper, we present a topological framework for studying signed permutations and their reversal distance. This framework is based on a presentation of orientable and non-orientable fatgraphs via sectors. As an application, we give an alternative approach and interpretation of the Hannenhalli–Pevzner formula for the reversal distance of sorting signed permutations. This is obtained by constructing a bijection between signed permutations and certain equivalence classes of fatgraphs, called π -maps. We study the action of reversals and show that they either splice, glue or half-flip external vertices, which implies that any reversal changes the topological genus by at most one. We show that the lower bound of the reversal distance of a signed permutation equals the topological genus of its π -maps. We then discuss how the new topological model connects to other sorting problems.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Katarzyna Rybarczyk, Dudley Stark Random intersection graphs are characterised by three parameters: n , m and p , where n is the number of vertices, m is the number of objects, and p is the probability that a given object is associated with a given vertex. Two vertices in a random intersection graph are adjacent if and only if they have an associated object in common. When m = ⌊ n α ⌋ for constant α , we provide a condition, called strictly α -balanced, for the Poisson convergence of the number of induced copies of a fixed subgraph.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Derek Garton Fix an odd prime ℓ and let G be the poset of isomorphism classes of finite abelian ℓ -groups, ordered by inclusion. If ξ : G → R ≥ 0 is a discrete probability distribution on G and A ∈ G , define the A th moment of ξ to be ∑ B ∈ G Surj ( B , A ) ξ ( B ) . The question of determining conditions that ensure ξ is completely determined by its moments has been of recent interest in many problems of Cohen–Lenstra type. Furthermore, recovering ξ from its moments requires a new Möbius-type inversion formula on G . In this paper, we define this function, relate it to the classical Möbius function on the poset of subgroups of a fixed group, and prove two theorems about when it vanishes. As one corollary of these theorems, we obtain an analog of Hall’s theorem on the vanishing of the classical Möbius function. As another, we obtain an infinite family of pairs of groups on which the classical Möbius function vanishes; obtaining such pairs is a group-theoretic topic of recent interest.

Abstract: Publication date: September 2017 Source:Discrete Mathematics, Volume 340, Issue 9 Author(s): Mircea Merca A relationship between the general linear group G L ( n , m ) and integer partitions was investigated by Macdonald in order to calculate the number of conjugacy classes in G L ( n , m ) . In this paper, the author introduced two different factorizations for a special case of Lambert series in order to prove that the number of conjugacy classes in the general linear group G L ( n , m ) and the number of partitions of n into k different magnitudes are related by a finite discrete convolution. New identities involving overpartitions, partitions into k different magnitudes and other combinatorial objects are discovered and proved in this context.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Vadim E. Levit, David Tankus Let G be a graph. A set S of vertices in G dominates the graph if every vertex of G is either in S or a neighbor of a vertex in S . Finding a minimum cardinality set which dominates the graph is an NP-complete problem. The graph G is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths 4 and 5 , by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function w is defined on the vertices of G . Then G is w -well-dominated if all its minimal dominating sets are of the same weight. We prove that the set of weight functions w such that G is w -well-dominated is a vector space, and denote that vector space by W W D ( G ) . We show that W W D ( G ) is a subspace of W C W ( G ) , the vector space of weight functions w such that G is w -well-covered. We provide a polynomial characterization of W W D ( G ) for the case that G does not contain cycles of lengths 4 , 5 , and 6 .

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Mi-Mi Zhang, Jin-Xin Zhou A graph is said to be a bi-Cayley graph over a group H if it admits H as a semiregular automorphism group with two vertex-orbits. A bi-dihedrant is a bi-Cayley graph over a dihedral group. In this paper, it is shown that every connected trivalent edge-transitive bi-dihedrant is also vertex-transitive, and then we present a classification of trivalent arc-transitive bi-dihedrants, and study the Cayley property of trivalent vertex-transitive bi-dihedrants.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Hui Zhou A graph with some graph symmetry property is top, if it cannot be viewed as a nontrivial normal quotient of some other graph with the same graph symmetry property. Therefore, a graph being top implies that it has no nontrivial normal multicovers, including normal covers. John Conway proved that every s -arc-transitive graph has a nontrivial s -arc-transitive normal cover, so there is no top s -arc-transitive graph. However, there exist top locally- s -distance-transitive graphs, and complete multipartite graphs are examples of this. In this paper, we give a generic condition for locally- s -distance-transitive graphs to be top. Also, examples and characterizations of graphs that admit this condition are given.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Liangchen Li By further exploring some ideas in Buratti (1999), Chang and Ding (2006) several new infinite classes of difference families from finite fields are obtained and some results of Chang and Ding (2006) are extended.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Dai-Qiang Hu, Jian-Liang Wu A graph G is k -choosable if it can be properly colored whenever every vertex has a list of at least k available colors. In the paper, it is proved that all planar graphs without intersecting 5 -cycles are 4 -choosable.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): R. Haas, K. Seyffarth Let G be a graph and let k be a positive integer. The k -dominating graph of G , denoted by D k ( G ) , has vertices corresponding to the dominating sets of G having cardinality at most k ; two vertices of D k ( G ) are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote by d 0 ( G ) the least value of k for which D k ( G ) is connected for all k ≥ d 0 ( G ) . It is known that d 0 ( G ) ≥ Γ ( G ) + 1 , where Γ ( G ) is the upper domination number of G . In this paper we prove that if G is a graph that is both perfect and irredundant perfect, or if G belongs to certain classes of well-covered graphs, then d 0 ( G ) = Γ ( G ) + 1 . In order to prove these results, we show that all independent dominating sets of a graph G are in the same component of D Γ ( G ) + 1 ( G ) .

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Daniel Horsley, Rosalind A. Hoyte 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: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Jianxin Wei, Yujun Yang, Guangfu Wang The generalized Fibonacci Q d ( f ) is defined as the graph obtained from the d -cube Q d by removing all vertices that contain a given binary string f as a contiguous substring. This idea was introduced by Ilić, Klavžar and Rho. A binary string f is called isometric if Q d ( f ) is an isometric subgraph of Q d for all d ≥ 1 , otherwise it is called non-isometric. In this paper, we prove that a string f is isometric if and only if f n is isometric for any n ≥ 1 . This result can help us to construct more isometric strings and significantly increase the number of isometric strings.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Jason J. Molitierno In this paper, we determine upper bounds on the algebraic connectivity, denoted as a ( G ) , of maximal outerplanar graphs. We show that if G is a maximal outerplanar graph on n ≥ 12 vertices not of the form K 1 ∨ P n − 1 , then a ( G ) ≤ 1 with equality holding for exactly two maximal outerplanar graphs on 12 vertices. We show this by assigning labels y 1 , … , y n to the vertices and showing the existence of vertex labellings such that ∑ u v ∈ E ( G ) ( y u − y v ) 2 ∕ ∑ v ∈ V ( G ) y v 2 < 1 .

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Young Soo Kwon In this paper, we consider the classification of nonorientable regular embeddings of cartesian products G d of a graph G . We show that if G is a bipartite graph and d ≥ 3 , then there is no nonorientable regular embedding. This is a generalization of the result that there is no nonorientable regular embeddings of Q n for n ≥ 3 shown by R. Nedela and the author in 2007. When G is non-bipartite and d ≥ 3 , we show that if there is a nonorientable regular embedding of G d , then there is a nonorientable regular embedding of G . Furthermore, we show that any nonorientable regular embedding of G d with d ≥ 3 is isomorphic to a Petrie dual of some orientable regular embedding of G d . Using these results, we classify the nonorientable regular embeddings of cartesian products C n d of a cycle C n ; for even n there is no nonorientable regular embedding except when d = 1 , and for odd n there is a unique nonorientable regular embedding for each d .

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): E. Abajo, G. Araujo-Pardo, C. Balbuena, M. Bendala A ( k , g ) -graph is a k -regular graph with girth g and a ( k , g ) -cage is a ( k , g ) -graph with the fewest possible number of vertices. The cage problem consists of constructing ( k , g ) -graphs of minimum order n ( k , g ) . We focus on girth g = 5 , where cages are known only for degrees k ≤ 7 . We construct ( k , 5 ) -graphs using techniques exposed by Funk (2009) and Abreu et al. (2012) to obtain the best upper bounds on n ( k , 5 ) known hitherto. The tables given in the introduction show the improvements obtained with our results.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Wuyang Sun Berge Conjecture states that every bridgeless cubic graph has 5 perfect matchings such that each edge is contained in at least one of them. In this paper, we show that Berge Conjecture holds for two classes of cubic graphs, cubic graphs with a circuit missing only one vertex and bridgeless cubic graphs having a 2-factor with exactly two circuits. The first part of this result implies that Berge Conjecture holds for hypohamiltonian cubic graphs.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Raquel Águeda, Valentin Borozan, Raquel Díaz, Yannis Manoussakis, Leandro Montero A c -edge-colored multigraph has each edge colored with one of the c available colors and no two parallel edges have the same color. A proper Hamiltonian cycle is a cycle containing all the vertices of the multigraph such that no two adjacent edges have the same color. In this work we establish sufficient conditions for a multigraph to have a proper Hamiltonian cycle, depending on several parameters such as the number of edges and the rainbow degree.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): S.C. López, F.A. Muntaner-Batle, M. Prabu The ⊗ h -product that is referred in the title was introduced in 2008 as a generalization of the Kronecker product of digraphs. Many relations among labelings have been obtained since then, always using as a second factor a family of super edge-magic graphs with equal order and size. In this paper, we introduce a new labeling construction by changing the role of the factors. Using this new construction the range of applications grows up considerably. In particular, we can increase the information about magic sums of cycles and crowns.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Hao Liu, Cunsheng Ding, Chengju Li BCH codes have been studied for over fifty years and widely employed in consumer devices, communication systems, and data storage systems. However, the dimension of BCH codes is settled only for a very small number of cases. In this paper, we study the dimensions of BCH codes over finite fields with three types of lengths n , namely n = q m − 1 , n = ( q m − 1 ) ∕ ( q − 1 ) and n = q m + 1 . For narrow-sense primitive BCH codes with designed distance δ , we investigate their dimensions for δ in the range 1 ≤ δ ≤ q ⌈ m 2 ⌉ + 1 . For non-narrow sense primitive BCH codes, we provide two general formulas on their dimensions and give the dimensions explicitly in some cases. Furthermore, we settle the minimum distances of some primitive BCH codes. We also explore the dimensions of the BCH codes of lengths n = ( q m − 1 ) ∕ ( q − 1 ) and n = q m + 1 over finite fields.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Ayşe Hümeyra Bilge, Derya Çelik, Şahin Koçak Let ( X , d ) be a finite metric space with elements P i , i = 1 , … , n and with the distance functions d i j . The Gromov Product of the “triangle” ( P i , P j , P k ) with vertices P i , P j and P k at the vertex P i is defined by Δ i j k = 1 ∕ 2 ( d i j + d i k − d j k ) . We show that the collection of Gromov products determines the metric. We call a metric space Δ -generic, if the set of all Gromov products at a fixed vertex P i has a unique smallest element (for i = 1 , … , n ). We consider the function assigning to each vertex P i the edge { P j , P k } of the triangle ( P i , P j , P k ) realizing the minimal Gromov product at P i and we call this function the Gromov product structure of the metric space ( X , d ) . We say two Δ -generic metric spaces ( X , d ) and ( X , d ′ ) to be Gromov product equivalent, if the corresponding Gromov product structures are the same up to a permutation of X . For n = 3 , 4 there is one ( Δ -generic) Gromov equivalence class and for n = 5 there are three ( Δ -generic) Gromov equivalence classes. For n = 6 we show by computer that there are 26 distinct ( Δ -gene... PubDate: 2017-05-10T13:00:39Z

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Hao Liang, Jun-Ming Xu This paper gives an approximate result related to Seymour’s Second Neighborhood conjecture, that is, for any m -free digraph G , there exists a vertex v ∈ V ( G ) and a real number λ m such that d + + ( v ) ≥ λ m d + ( v ) , and λ m → 1 while m → + ∞ . This result generalizes and improves some known results in a sense.

Abstract: Publication date: August 2017 Source:Discrete Mathematics, Volume 340, Issue 8 Author(s): Ngo Dac Tan We raise the conjecture that for every integer g ≥ 3 there are only finitely many 3-regular digraphs of girth g without vertex disjoint directed cycles of different lengths and give support for this conjecture by proving that it is true for g = 3 .