Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): L. Alcón, M. Gutierrez, M.P. Mazzoleni The edge-intersection graph of a family of paths on a host tree is called an E P T graph. When the tree has maximum degree h , we say that the graph is [ h , 2 , 2 ] . If, in addition, the family of paths satisfies the Helly property, then the graph is Helly [ h , 2 , 2 ] . In this paper, we present a family of E P T graphs called gates which are forbidden induced subgraphs for [ h , 2 , 2 ] graphs. Using these we characterize by forbidden induced subgraphs the Helly [ h , 2 , 2 ] graphs. As a byproduct we prove that in getting a Helly E P T -representation, it is not necessary to increase the maximum degree of the host tree. In addition, we give an efficient algorithm to recognize Helly [ h , 2 , 2 ] graphs based on their decomposition by maximal clique separators.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Ivica Martinjak Let B be a biplane of order k − 2 represented by a canonical incidence matrix M . We prove that for the principal submatrix of order k − 2 starting at the ( k + 1 ) st row and column of M there are at most k − 2 values up to isomorphism. This result provides almost trivial classification of biplanes up to order 7 .

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Kijung Kim, Sung-Yell Song, Bangteng Xu In this paper, we give a new class of association schemes whose thin residues are isomorphic to an elementary abelian p -group of order p 2 . We then study the automorphism groups of these schemes and determine whether these schemes are schurian.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Francesco Brenti, Angela Carnevale We define a new statistic on the even hyperoctahedral groups which is a natural analogue of the odd length statistic recently defined and studied on Coxeter groups of types A and B . We compute the signed (by length) generating function of this statistic over the whole group and over its maximal and some other quotients and show that it always factors nicely. We also present some conjectures.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Shane Chern We study the generating function for overpartitions with bounded differences between largest and smallest parts, which is analogous to a result of Breuer and Kronholm on integer partitions. We also connect this problem with over q -binomial coefficients introduced by Dousse and Kim.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Yuan Cao, Yonglin Cao, Fanghui Ma Let F 2 m be a finite field of cardinality 2 m , R = F 2 m [ u ] ∕ 〈 u 4 〉 and n be an odd positive integer. For any δ , α ∈ F 2 m × , ideals of the ring R [ x ] ∕ 〈 x 2 n − ( δ + α u 2 ) 〉 are identified as ( δ + α u 2 ) -constacyclic codes of length 2 n over R . In this paper, an explicit representation and enumeration for all distinct ( δ + α u 2 ) -constacyclic codes of length 2 n over R are presented.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Matheus Bernardini, Fernando Torres Let n g be the number of numerical semigroups of genus g . We present an approach to compute n g by using even gaps, and the question: Is it true that n g + 1 > n g ' is investigated. Let N γ ( g ) be the number of numerical semigroups of genus g whose number of even gaps equals γ . We show that N γ ( g ) = N γ ( 3 γ ) for γ ≤ ⌊ g ∕ 3 ⌋ and N γ ( g ) = 0 for γ > ⌊ 2 g ∕ 3 ⌋ ; thus the question above is true provided that N γ ( g + 1 ) > N γ ( g ) for γ = ⌊ g ∕ 3 ⌋ + 1 , … , ⌊ 2 g ∕ 3 ⌋ . We also show that N γ ( 3 γ ) coincides with f γ , the number introduced by Bras-Amorós (2012) in connection with semigroup-closed sets. Finally, the stronger possibility f γ ∼ φ 2 γ arises being φ = ( 1 + 5 ) ∕ 2 the golden number.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Jiang Zhou, Lizhu Sun, Changjiang Bu A weighted (unweighted) graph G is called equiarboreal if the sum of weights (the number) of spanning trees containing a given edge in G is independent of the choice of edge. In this paper, we give some resistance characterizations of equiarboreal weighted and unweighted graphs, and obtain the necessary and sufficient conditions for k -subdivision graphs, iterated double graphs, line graphs of regular graphs and duals of planar graphs to be equiarboreal. Applying these results, we obtain new infinite families of equiarboreal graphs, including iterated double graphs of 1-walk-regular graphs, line graphs of triangle-free 2-walk-regular graphs, and duals of equiarboreal planar graphs.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Shuya Chiba, Tomoki Yamashita Let G be a balanced bipartite graph of order 2 n ≥ 4 , and let σ 1 , 1 ( G ) be the minimum degree sum of two non-adjacent vertices in different partite sets of G . In 1963, Moon and Moser proved that if σ 1 , 1 ( G ) ≥ n + 1 , then G is hamiltonian. In this note, we show that if k is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly k cycles for sufficiently large graphs. In order to prove this, we also give a σ 1 , 1 condition for the existence of k vertex-disjoint alternating cycles with respect to a chosen perfect matching in G .

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Megan Cream, Ronald J. Gould, Victor Larsen We call a graph G pancyclic if it contains at least one cycle of every possible length m , for 3 ≤ m ≤ V ( G ) . In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length 4 , 5 , … , V ( G ) . In particular, certain paths and triangles with pendant paths are forbidden.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Wei Meng, Jia Guo, Mei Lu, Yubao Guo, Lutz Volkmann An arc u v of a digraph D is called universal if u v and w are in a common cycle for any vertex w of D . In this paper we characterize local tournaments whose every arc is universal.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): R. Julian R. Abel, Diana Combe, Adrian M. Nelson, William D. Palmer We introduce a new piecewise construction technique for generalised Bhaskar Rao designs and the concepts of generalised Bhaskar Rao block design pieces and holey generalised Bhaskar Rao block designs. We prove composition theorems for these designs. Using this construction technique and the theory of group representations, and the representations of 2 -groups over the field with 3 elements, we show that the established necessary conditions for the existence of generalised Bhaskar Rao designs of block size 3 are sufficient for all groups of order 2 n 3 m .

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Terry A. McKee The i-triangulated graphs, introduced by Tibor Gallai in the early 1960s, have a number of characterizations—one of the simplest is that every odd cycle of length 5 or more has noncrossing chords. A variety of new characterizations are proved, starting with a simple forbidden induced subgraph characterization and including the following two: (1) Every 2-connected induced subgraph H is bipartite or chordal or, for every induced even cycle C of H , the intersection of the neighborhoods in H of all the vertices of C induces a complete multipartite subgraph. (2) For every 2-connected induced subgraph H that is not bipartite, every cardinality-2 minimal vertex separator of H induces an edge.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Jean-Luc Baril, Sergey Kirgizov, Vincent Vajnovszki We study the distribution and the popularity of left children on sets of treeshelves avoiding a pattern of size three. (Treeshelves are ordered binary increasing trees where every child is connected to its parent by a left or a right link.) The considered patterns are sub-treeshelves, and for each such a pattern we provide exponential generating function for the corresponding distribution and popularity. Finally, we present constructive bijections between treeshelves avoiding a pattern of size three and some classes of simpler combinatorial objects.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Junqing Cai, Hao Li, Qiang Sun Let σ 4 ∗ = min { ∑ i = 1 4 d ( v i ) + ⋃ i = 1 4 N ( v i ) − ⋂ i = 1 4 N ( v i ) : { v 1 , v 2 , v 3 , v 4 } is an independent set of a graph G } . In this paper, we give a low bound for the length of a longest cycle in a 4-connected graph and get the following result: If G is a 4-connected graph on n vertices, then the circumference c ( G ) ≥ min { n , σ 4 ∗ ∕ 2 } . Moreover, we give graphs to show that the connectivity in our result is best possible with respect to the low bound and the low bound in our result is also best possible with respect to the connectivity.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Yian Xu Bamberg and Giudici (2011) showed that the point graphs of certain generalised quadrangles of order ( q − 1 , q + 1 ) , where q = p k is a prime power with p ≥ 5 , are both normal and non-normal Cayley graphs for two isomorphic groups. We call these graphs BG-graphs. In this paper, we show that the Cayley graphs obtained from a finite number of BG-graphs by Cartesian product, direct product, and strong product also possess the property of being normal and non-normal Cayley graphs for two isomorphic groups.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): R.E.L. Aldred, Jun Fujisawa, Akira Saito A matching M in a graph G is said to be extendable if there exists a perfect matching of G containing M . In 1989, it was shown that every connected planar graph with at least 8 vertices has a matching of size three which is not extendable. In contrast, the study of extending certain matchings of size three or more has made progress in the past decade when the given graph is 5 -connected planar triangulation or 5 -connected plane graphs with few non-triangular faces. In this paper, we prove that if G is a 5 -connected plane graph of even order in which at most two faces are not triangular and M is a matching of size four in which the edges lie pairwise distance at least three apart, then M is extendable. A related result concerning perfect matching with proscribed edges is shown as well.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Houmem Belkhechine Given a tournament T , a module of T is a subset X of V ( T ) such that for x , y ∈ X and v ∈ V ( T ) ∖ X , ( x , v ) ∈ A ( T ) if and only if ( y , v ) ∈ A ( T ) . The trivial modules of T are ∅ , { u } ( u ∈ V ( T ) ) and V ( T ) . The tournament T is indecomposable if all its modules are trivial; otherwise it is decomposable. The decomposability index of T , denoted by δ ( T ) , is the smallest number of arcs of T that must be reversed to make T indecomposable. For n ≥ 5 , let δ ( n ) be the maximum of δ ( T ) over the tournaments T with n vertices. We prove that n + 1 4 ≤ δ ( n ) ≤ n − 1 3 and that the lower bound is reached by the transitive tournaments.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Wei Xiong, Jinquan Xu, Zhengke Miao, Yang Wu, Hong-Jian Lai For a graph G , the supereulerian width μ ′ ( G ) of a graph G is the largest integer s such that G has a spanning ( k ; u , v ) -trail-system, for any integer k with 1 ≤ k ≤ s , and for any u , v ∈ V ( G ) with u ≠ v . Thus μ ′ ( G ) ≥ 2 implies that G is supereulerian, and so graphs with higher supereulerian width are natural generalizations of supereulerian graphs. Settling an open problem of Bauer, Catlin (1988) proved that if a simple graph G on n ≥ 17 vertices satisfy δ ( G ) ≥ n 4 − 1 , then μ ′ ( G ) ≥ 2 . In this paper, we show that for any real numbers a , b with 0 < a < 1 and any integer s > 0 , there exists a finite graph family F = F ( a , b , s ) such that for a simple graph G with n = V ( G ) , if for any u , v ∈ V ( G ) with u v ⁄ ∈ E ( G ) , max { d G ( u ) , d G ( v ) } ≥ a n + b , then either μ ′ ( G ) ≥ s + 1 or G is contractible to a member in F . When a = 1 4 , b = − 3 2 , we show that if n is sufficiently large, PubDate: 2017-09-18T22:33:16Z

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Xun-Tuan Su The flows on rooted trees were recently introduced in the study of the free Pre-Lie group. In this paper, we establish a bijection between the closed flows on specific rooted trees called forks and the classical ballot paths. As a consequence, an enumeration formula conjectured by F. Chapoton is bijectively proved.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Xiuyun Wang The double generalized Petersen graph D P ( n , t ) , n ≥ 3 and t ∈ Z n ∖ { 0 } , 2 ≤ 2 t < n , has vertex-set { x i , y i , u i , v i ∣ i ∈ Z n } , edge-set { { x i , x i + 1 } , { y i , y i + 1 } , { u i , v i + t } , { v i , u i + t } , { x i , u i } , { y i , v i } ∣ i ∈ Z n } . These graphs were first defined by Zhou and Feng as examples of vertex-transitive non-Cayley graphs. Then, Kutnar and Petecki considered the structural properties, Hamiltonicity properties, vertex-coloring and edge-coloring of D P ( n , t ) , and conjectured that all D P ( n , t ) are Hamiltonian. In this paper, we prove this conjecture.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Ryuji Abe, Benoît Rittaud Let N ( 2 ) and N ( 5 ) be the sets of integer solutions of 2 x 2 + y 1 2 + y 2 2 = 4 x y 1 y 2 and 5 x 2 + y 1 2 + y 2 2 = 5 x y 1 y 2 , respectively. The elements of these sets give sequences in the non-discrete part of the Markoff spectrum consisting of the normalized values of arithmetic minima of indefinite quadratic forms. Each of these sets can be represented by a bipartite graph. Using this we can construct quadratic forms giving the values of the sequences. We show that, for a quadratic form f which gives a value of the Markoff spectrum corresponding to an integer solution x of N ( 2 ) and N ( 5 ) , the roots of f ( ξ , 1 ) = 0 have a periodic continued fraction expansion and the period is a palindrome with fixed prefix and suffix on { 1 , 2 , 3 } and { 1 , 2 , 3 , 4 } , respectively.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Louis Deaett, H. Tracy Hall The unique Steiner triple system of order 7 has a point-block incidence graph known as the Heawood graph. Motivated by questions in combinatorial matrix theory, we consider the problem of constructing a faithful orthogonal representation of this graph, i.e., an assignment of a vector in C d to each vertex such that two vertices are adjacent precisely when assigned nonorthogonal vectors. We show that d = 10 is the smallest number of dimensions in which such a representation exists, a value known as the minimum semidefinite rank of the graph, and give such a representation in 10 real dimensions. We then show how the same approach gives a lower bound on this parameter for the incidence graph of any Steiner triple system, and highlight some questions concerning the general upper bound.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Deng Tang, Claude Carlet, Zhengchun Zhou Binary linear codes with good parameters have important applications in secret sharing schemes, authentication codes, association schemes, and consumer electronics and communications. In this paper, we construct several classes of binary linear codes from vectorial Boolean functions and determine their parameters, by further studying a generic construction developed by Ding et al. recently. First, by employing perfect nonlinear functions and almost bent functions, we obtain several classes of six-weight linear codes which contain the all-one codeword, and determine their weight distribution. Second, we investigate a subcode of any linear code mentioned above and consider its parameters. When the vectorial Boolean function is a perfect nonlinear function or a Gold function in odd dimension, we can completely determine the weight distribution of this subcode. Besides, our linear codes have larger dimensions than the ones by Ding et al.’s generic construction.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): F. Larrión, M.A. Pizaña, R. Villarroel-Flores We study strong graph bundles : a concept imported from topology which generalizes both covering graphs and product graphs. Roughly speaking, a strong graph bundle always involves three graphs E , B and F and a projection p : E → B with fiber F (i.e. p − 1 x ≅ F for all x ∈ V ( B ) ) such that the preimage of any edge x y of B is trivial (i.e. p − 1 x y ≅ K 2 ⊠ F ). Here we develop a framework to study which subgraphs S of B have trivial preimages (i.e. p − 1 S ≅ S ⊠ F ) and this allows us to compare and classify several variations of the concept of strong graph bundle. As an application, we show that the clique operator preserves triangular graph bundles (strong graph bundles where preimages of triangles are trivial) thus yielding a new technique for the study of clique divergence of graphs.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Sheng-Liang Yang, Yan-Ni Dong, Tian-Xiao He Merlini and Sprugnoli (2017) give both an algebraic and a combinatorial proof for an identity proposed by Louis Shapiro by using Riordan arrays and a particular model of lattice paths. In this paper, we revisit the identity and emphasize the use of colored partial Motzkin paths as appropriate tool. By using colored Motzkin paths with weight defined according to the height of its last point, we can generalize the identity in several ways. These identities allow us to move from Fibonacci polynomials, Lucas polynomials, and Chebyshev polynomials, to the polynomials of the form ( z + b ) n .

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Lili Mu, Yi Wang, Yeong-Nan Yeh Let ( a n ) n ≥ 0 be a sequence of the Catalan-like numbers. We evaluate Hankel determinants det [ λ a i + j + μ a i + j + 1 ] 0 ≤ i , j ≤ n and det [ λ a i + j + 1 + μ a i + j + 2 ] 0 ≤ i , j ≤ n for arbitrary coefficients λ and μ . Our results unify many known results of Hankel determinant evaluations for classic combinatorial counting coefficients, including the Catalan, Motzkin and Schröder numbers.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Zhi-Hong Chen For a graph H , let σ t ( H ) = min { Σ i = 1 t d H ( v i ) { v 1 , v 2 , … , v t } is an independent set in H } and let U t ( H ) = min { ⋃ i = 1 t N H ( v i ) { v 1 , v 2 , ⋯ , v t } is an independent set in H } . We show that for a given number ϵ and given integers p ≥ t > 0 , k ∈ { 2 , 3 } and N = N ( p , ϵ ) , if H is a k -connected claw-free graph of order n > N with δ ( H ) ≥ 3 and its Ryjác̆ek’s closure c l ( H ) = L ( G ) , and if d t ( H ) ≥ t ( n + ϵ ) ∕ p where d t ( H ) ∈ { σ t ( H ) , U t ( H ) } , then either H is Hamiltonian or G , the preimage of L ( G ) , can be contracted to a k -edge-connected K 3 -free graph of order at most max { 4 p − 5 , 2 p + 1 } and without spanning closed trails. As applications, we prove the following for such graphs PubDate: 2017-09-18T22:33:16Z

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Seungsang Oh An independent vertex set of a graph is a set of vertices of the graph in which no two vertices are adjacent, and a maximal independent set is one that is not a proper subset of any other independent set. In this paper we count the number of maximal independent sets of vertices on a complete rectangular grid graph. More precisely, we provide a recursive matrix-relation producing the partition function with respect to the number of vertices. The asymptotic behavior of the maximal hard square entropy constant is also provided. We adapt the state matrix recursion algorithm, recently invented by the author to answer various two-dimensional regular lattice model problems in enumerative combinatorics and statistical mechanics.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Jesse T. Geneson, Peter M. Tian Pattern avoidance is a central topic in graph theory and combinatorics. Pattern avoidance in matrices has applications in computer science and engineering, such as robot motion planning and VLSI circuit design. A d -dimensional zero–one matrix A avoids another d -dimensional zero–one matrix P if no submatrix of A can be transformed to P by changing some ones to zeros. A fundamental problem is to study the maximum number of nonzero entries in a d -dimensional n × ⋯ × n matrix that avoids P . This maximum number, denoted by f ( n , P , d ) , is called the extremal function. We advance the extremal theory of matrices in two directions. The methods that we use come from combinatorics, probability, and analysis. Firstly, we obtain non-trivial lower and upper bounds on f ( n , P , d ) when n is large for every d -dimensional block permutation matrix P . We establish the tight bound Θ ( n d − 1 ) on f ( n , P , d ) for every d -dimensional tuple permutation matrix P . This tight bound has the lowest possible order that an extremal function of a nontrivial matrix can ever achieve. Secondly, we show that the limit inferior of the sequence { f ( n , P , d ) n d − 1 } has a lower bound 2 Ω ( k 1 ∕ 2 ) for a family of k × ⋯ × k permutation matrices P . We also improve the upper bound on the limit superior from 2 O ( k log k ) to 2 O ( k ) for all k × ⋯ × k permutation matrices and show that the new upper bound also holds for tuple permutation matrices.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Changhong Lu, Bing Wang, Ping Zhang A conjecture of Gyárfás and Sárközy says that in every 2 -coloring of the edges of the complete k -uniform hypergraph K n k , there are two disjoint monochromatic loose paths of distinct colors such that they cover all but at most k − 2 vertices. A weaker form of this conjecture with 2 k − 5 uncovered vertices instead of k − 2 is proved. Thus the conjecture holds for k = 3 . The main result of this paper states that the conjecture is true for all k ≥ 3 .

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Shipeng Wang, Liming Xiong Let H = { H 1 , … , H k } be a set of connected graphs. A graph is said to be H -free if it does not contain any member of H as an induced subgraph. We show that if the following statements hold, • H ≥ 2 , • K 1 , 3 ∈ H , • for any integer n 0 , every 2 -connected H -free graph G of order at least n 0 is supereulerian, i . e . , G has a spanning closed trail, then H ∖ { K 1 , 3 } contains an N i , j , k or a path where N i , j , k denotes the graph obtained by attaching three vertex-disjoint paths of lengths i , j , k ≥ 0 to a triangle. As an application, we characterize all the forbidden triples H with K 1 , 3 ∈ H such that every 2 -connected H -free graph is supereulerian. As a byproduct, we also characterize minimal 2-connected non-supereulerian claw-free graphs.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Denis S. Krotov A subspace bitrade of type T q ( t , k , v ) is a pair ( T 0 , T 1 ) of two disjoint nonempty collections of k -dimensional subspaces of a v -dimensional space V over the finite field of order q such that every t -dimensional subspace of V is covered by the same number of subspaces from T 0 and T 1 . In a previous paper, the minimum cardinality of a subspace T q ( t , t + 1 , v ) bitrade was established. We generalize that result by showing that for admissible v , t , and k , the minimum cardinality of a subspace T q ( t , k , v ) bitrade does not depend on k . An example of a minimum bitrade is represented using generator matrices in the reduced echelon form. For t = 1 , the uniqueness of a minimum bitrade is proved.

Abstract: Publication date: December 2017 Source:Discrete Mathematics, Volume 340, Issue 12 Author(s): Dylan Heuer, Chelsey Morrow, Ben Noteboom, Sara Solhjem, Jessica Striker, Corey Vorland We define and enumerate two new two-parameter permutation families, namely, placements of a maximum number of non-attacking rooks on k chained-together n × n chessboards, in either a circular or linear configuration. The linear case with k = 1 corresponds to standard permutations of n , and the circular case with n = 4 and k = 6 corresponds to a three-person chessboard. We give bijections of these rook placements to matrix form, one-line notation, and matchings on certain graphs. Finally, we define chained linear and circular alternating sign matrices, enumerate them for certain values of n and k , and give bijections to analogues of monotone triangles, square ice configurations, and fully-packed loop configurations.

Abstract: Publication date: November 2017 Source:Discrete Mathematics, Volume 340, Issue 11 Author(s): Krystal Guo, Bojan Mohar It is well-known that the paths are determined by the spectrum of the adjacency matrix. For digraphs, every digraph whose underlying graph is a tree is cospectral to its underlying graph with respect to the Hermitian adjacency matrix ( H -cospectral). Thus every (simple) digraph whose underlying graph is isomorphic to P n is H -cospectral to P n . Interestingly, there are others. This paper finds digraphs that are H -cospectral with the path graph P n and whose underlying graphs are nonisomorphic, when n is odd, and finds that such graphs do not exist when n is even. In order to prove this result, all digraphs whose Hermitian spectral radius is smaller than 2 are determined.

Abstract: Publication date: November 2017 Source:Discrete Mathematics, Volume 340, Issue 11 Author(s): Gábor Bacsó, Zdeněk Ryjáček, Zsolt Tuza The weak chromatic number, or clique chromatic number (CCHN) of a graph is the minimum number of colors in a vertex coloring, such that every maximal clique gets at least two colors. The weak chromatic index, or clique chromatic index (CCHI) of a graph is the CCHN of its line graph. Most of the results here are upper bounds for the CCHI, as functions of some other graph parameters, and contrasting with lower bounds in some cases. Algorithmic aspects are also discussed; the main result within this scope (and in the paper) shows that testing whether the CCHI of a graph equals 2 is NP-complete. We deal with the CCHN of the graph itself as well.

Abstract: Publication date: November 2017 Source:Discrete Mathematics, Volume 340, Issue 11 Author(s): Simon Jäger, Dieter Rautenbach For a set S of vertices of a graph G , a vertex u in V ( G ) ∖ S , and a vertex v in S , let dist ( G , S ) ( u , v ) be the distance of u and v in the graph G − ( S ∖ { v } ) . Dankelmann et al. (2009) define S to be an exponential dominating set of G if w ( G , S ) ( u ) ≥ 1 for every vertex u in V ( G ) ∖ S , where w ( G , S ) ( u ) = ∑ v ∈ S 1 2 dist ( G , S ) ( u , v ) − 1 . Inspired by this notion, we define S to be an exponential independent set of G if w ( G , S ∖ { u } ) ( u ) < 1 for every vertex u in S , and the exponential independence number α e ( G ) of G as the maximum order of an exponential independent set of G . Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs G for which α e ( H ) equals the independence number α ( H ) for every induced subgraph H of G , and we give an explicit characterization of all trees T with α e ... PubDate: 2017-08-31T21:43:06Z

Abstract: Publication date: November 2017 Source:Discrete Mathematics, Volume 340, Issue 11 Author(s): Ts.Ch-D. Batueva, O.V. Borodin, M.A. Bykov, A.O. Ivanova, O.N. Kazak, D.V. Nikiforov The weight w ( e ) of an edge e in a normal plane map (NPM) is the degree-sum of its end-vertices. An edge e = u v is of type ( i , j ) if d ( u ) ≤ i and d ( v ) ≤ j . In 1940, Lebesgue proved that every NPM has an edge of one of the types ( 3 , 11 ) , ( 4 , 7 ) , or ( 5 , 6 ) , where 7 and 6 are best possible. In 1955, Kotzig proved that every 3-connected planar graph has an edge e with w ( e ) ≤ 13 , which bound is sharp. Borodin (1989), answering Erdős’ question, proved that every NPM has either a ( 3 , 10 ) -edge, or ( 4 , 7 ) -edge, or ( 5 , 6 ) -edge. A vertex is simplicial if it is completely surrounded by 3-faces. In 2010, Ferencová and Madaras conjectured (in different terms) that every 3-polytope without simplicial 3-vertices has an edge e with w ( e ) ≤ 12 . Recently, we confirmed this conjecture by proving that every NPM has either a simplicial 3-vertex adjacent to a vertex of degree at most 10, or an edge of types ( 3 , 9 ) , ( 4 , 7 ) , or ( 5 , 6 ) . By a k ( ℓ ) -vertex we mean a k -vertex incident with precisely ℓ triangular faces. The purpose of our paper is to prove that every NPM has an edge of one of the following types: ( 3 ( 3 ) , 10 ) , ( 3 ( 2 ) , 9 ) , ( 3 ( 1 ) , 7 ) , ( 4 ( 4 ) , 7 ) , ( 4 ( 3 ) , 6 ) , ( 5 ( 5 ) , PubDate: 2017-08-31T21:43:06Z

Abstract: Publication date: November 2017 Source:Discrete Mathematics, Volume 340, Issue 11 Author(s): Michael D. Plummer, Akira Saito A connected graph G with at least 2 m + 2 n + 2 vertices is said to satisfy the property E ( m , n ) if G contains a perfect matching and for any two sets of independent edges M and N with M = m and N = n with M ∩ N = ∅ , there is a perfect matching F in G such that M ⊂ F and N ∩ F = ∅ . In particular, if G is E ( m , 0 ) , we say that G is m -extendable. One of the authors has proved that every m -tough graph of even order at least 2 m + 2 is m -extendable (Plummer, 1988). Chen (1995) and Robertshaw and Woodall (2002) gave sufficient conditions on binding number for m -extendability. In this paper, we extend these results and give lower bounds on toughness and binding number which guarantee E ( m , n ) .

Abstract: Publication date: November 2017 Source:Discrete Mathematics, Volume 340, Issue 11 Author(s): Susan A. van Aardt, Christoph Brause, Alewyn P. Burger, Marietjie Frick, Arnfried Kemnitz, Ingo Schiermeyer An edge-coloured graph G is called properly connected if any two vertices are connected by a path whose edges are properly coloured. 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. Our main result is the following: Let G be a connected graph of order n and k ≥ 2 . If E ( G ) ≥ n − k − 1 2 + k + 2 , then pc ( G ) ≤ k except when k = 2 and G ∈ { G 1 , G 2 } , where G 1 = K 1 ∨ ( 2 K 1 + K 2 ) and G 2 = K 1 ∨ ( K 1 + 2 K 2 ) .