The Electronic Journal of Combinatorics
http://www.combinatorics.org/ojs/index.php/eljc
<p>The Electronic Journal of Combinatorics (E-JC) is a fully-refereed electronic journal with <em>very high standards,</em> publishing papers of substantial content and interest in all branches of discrete mathematics, including combinatorics, graph theory, and algorithms for combinatorial problems. The journal is <em>completely free</em> for both authors and readers. Authors retain the copyright of their articles and are strongly encouraged to release their articles under a Creative Commons license. Articles published in E-JC are reviewed on MathSciNet and ZBMath, and are indexed by Web of Science. The latest papers are always available by clicking on the tab marked "Current" near the top of the page. You can also locate papers using the search facility on the right hand side of this page.</p><p>E-JC was founded in 1994 by Herbert S. Wilf and Neil Calkin, making it one of the oldest electronic journals. E-JC is a founding member of the <a href="http://freejournals.org/" target="_blank">Free Journal Network</a>. </p>en-US<p>The copyright of published papers remains with the authors. We only require your agreement that we publish it, as described in the following publication release agreement:</p><ol><li>This is an agreement between the Electronic Journal of Combinatorics (the "Journal"), and the copyright owner (the "Owner") of a work (the "Work") to be published in the Journal.</li><li>The Owner warrants that s/he has the full power and authority to enter into this Agreement and to grant the rights granted in this Agreement.</li><li>The Owner hereby grants to the Journal a worldwide, irrevocable, royalty free license to publish or distribute the Work, to enter into arrangements with others to publish or distribute the Work, and to archive the Work.</li><li>The Owner agrees to ensure, to the extent reasonably possible, that further publication of the Work with the same or substantially the same content will include an acknowledgement of prior publication in the Journal.</li></ol><p>Published papers will contain a copyright notice indicating that copyright is held by the authors. In addition, we strongly encourage authors to release their paper under one of the <a title="Creative Commons" href="https://creativecommons.org/licenses/" target="_blank">Creative Commons licenses</a>.</p><p>Most papers published before March 31, 2018 did not contain explicit copyright or license statements. In those cases, authors agreed to items 1-3 above and to the following version of item 4: "The Owner agrees that further publication of the Work, with the same or substantially the same content as appears in the Journal, will include an acknowledgement of prior publication in the Journal."</p>mattbeck@sfsu.edu (Matt Beck)bdm@cs.anu.edu.au (Brendan McKay)Fri, 13 Apr 2018 11:43:14 +1000OJS 2.4.8.2http://blogs.law.harvard.edu/tech/rss60Sharp Lower Bounds on the Spectral Radius of Uniform Hypergraphs Concerning Degrees
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p1
Let $\mathcal{A}(H)$ and $\mathcal{Q}(H)$ be the adjacency tensor and signless Laplacian tensor of an $r$-uniform hypergraph $H$. Denote by $\rho(H)$ and $\rho(\mathcal{Q}(H))$ the spectral radii of $\mathcal{A}(H)$ and $\mathcal{Q}(H)$, respectively. In this paper we present a lower bound on $\rho(H)$ in terms of vertex degrees and we characterize the extremal hypergraphs attaining the bound, which solves a problem posed by Nikiforov [Analytic methods for uniform hypergraphs, Linear Algebra Appl. 457 (2014) 455<span>–</span>535]. Also, we prove a lower bound on $\rho(\mathcal{Q}(H))$ concerning degrees and give a characterization of the extremal hypergraphs attaining the bound.Liying Kang, Lele Liu, Erfang Shan
Copyright (c) 2018
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p1Fri, 13 Apr 2018 00:00:00 +1000Eigenvalue Bounds for the Signless $p$-Laplacian
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p2
We consider the signless $p$-Laplacian $Q_p$ of a graph, a generalisation of the quadratic form of the signless Laplacian matrix (the case $p=2$). In analogy to Rayleigh's principle the minimum and maximum of $Q_p$ on the $p$-norm unit sphere are called its smallest and largest eigenvalues, respectively. We show a Perron-Frobenius property and basic inequalites for the largest eigenvalue and provide upper and lower bounds for the smallest eigenvalue in terms of a graph parameter related to the bipartiteness. The latter result generalises bounds by Desai and Rao and, interestingly, at $p=1$ upper and lower bounds coincide.Elizandro Max Borba, Uwe Schwerdtfeger
Copyright (c) 2018
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p2Fri, 13 Apr 2018 00:00:00 +1000Residual $q$-Fano Planes and Related Structures
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p3
<p>One of the most intriguing problems for $q$-analogs of designs, is the existence question of an infinite family of $q$-Steiner systems that are not spreads. In particular the most interesting case is the existence question for the $q$-analog of the Fano plane, known also as the $q$-Fano plane. These questions are in the front line of open problems in block design. There was a common belief and a conjecture that such structures do not exist. Only recently, $q$-Steiner systems were found for one set of parameters. In this paper, a definition for the $q$-analog of the residual design is presented. This new definition is different from previous known definition, but its properties reflect better the $q$-analog properties. The existence of a design with the parameters of the residual $q$-Steiner system in general and the residual $q$-Fano plane in particular are examined. We construct different residual $q$-Fano planes for all $q$, where $q$ is a prime power. The constructed structure is just one step from a construction of a $q$-Fano plane.</p>Tuvi Etzion, Niv Hooker
Copyright (c) 2018
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p3Tue, 03 Apr 2018 18:41:29 +1000On the Poset and Asymptotics of Tesler Matrices
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p4
<p>Tesler matrices are certain integral matrices counted by the Kostant partition function and have appeared recently in Haglund's study of diagonal harmonics. In 2014, Drew Armstrong defined a poset on such matrices and conjectured that the characteristic polynomial of this poset is a power of $q-1$. We use a method of Hallam and Sagan to prove a stronger version of this conjecture for posets of a certain class of generalized Tesler matrices. We also study bounds for the number of Tesler matrices and how they compare to the number of parking functions, the dimension of the space of diagonal harmonics.</p>Jason O'Neill
Copyright (c) 2018 Jason O'Neill
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p4Fri, 13 Apr 2018 00:00:00 +1000Hamilton Circles in Cayley Graphs
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p5
<p>For locally finite infinite graphs the notion of Hamilton cycles can be extended to Hamilton circles, homeomorphic images of $S^1$ in the Freudenthal compactification. In this paper we prove a sufficient condition for the existence of Hamilton circles in locally finite Cayley graphs.</p>Babak Miraftab, Tim Rühmann
Copyright (c) 2018
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p5Tue, 03 Apr 2018 19:07:09 +1000On the Existence of Frobenius Digraphical Representations
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p6
<p>A Frobenius group is a transitive permutation group that is not regular and such that only the identity fixes more than one point. A digraphical, respectively graphical, Frobenius representation, DFR and GFR for short, of a Frobenius group $F$ is a digraph, respectively graph, whose automorphism group as a group of permutations of the vertex set is $F$. The problem of classifying which Frobenius groups admit a DFR and GFR has been proposed by Mark Watkins and Thomas Tucker and is a natural extension of the problem of classifying which groups that have a digraphical, respectively graphical, regular representation.</p><p>In this paper, we give a partial answer to a question of Mark Watkins and Thomas Tucker concerning Frobenius representations: "All but finitely many Frobenius groups with a given Frobenius complement have a DFR".</p><p> </p><p> </p>Pablo Spiga
Copyright (c) 2018
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p6Tue, 03 Apr 2018 19:27:12 +1000Even Subgraph Expansions for the Flow Polynomial of Planar Graphs with Maximum Degree at Most 4
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p7
<p>As projections of links, 4-regular plane graphs are important in combinatorial knot theory. The flow polynomial of 4-regular plane graphs has a close relation with the two-variable Kauffman polynomial of links. F. Jaeger in 1991 provided even subgraph expansions for the flow polynomial of cubic plane graphs. Starting from and based on Jaeger's work, by introducing splitting systems of even subgraphs, we extend Jaeger's results from cubic plane graphs to plane graphs with maximum degree at most 4 including 4-regular plane graphs as special cases. Several consequences are derived and further work is discussed.</p>Qingying Deng, Xian'an Jin, Fengming Dong, Eng Guan Tay
Copyright (c) 2018 The Electronic Journal of Combinatorics
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p7Tue, 03 Apr 2018 19:51:28 +1000A New Approach for Examining $q$-Steiner Systems
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p8
<p>One of the most intriguing problems in $q$-analogs of designs and codes is the existence question of an infinite family of $q$-analog of Steiner systems (spreads not included) in general, and the existence question for the $q$-analog of the Fano plane in particular.</p><p>We exhibit a completely new method to attack this problem. In the process we define a new family of designs whose existence is implied by the existence of $q$-Steiner systems, but could exist even if the related $q$-Steiner systems do not exist.</p><p>The method is based on a possible system obtained by puncturing all the subspaces of the $q$-Steiner system several times. We define the punctured system as a new type of design and enumerate the number of subspaces of various types that it might have. It will be evident that its existence does not imply the existence of the related $q$-Steiner system. On the other hand, this type of design demonstrates how close can we get to the related $q$-Steiner system.</p><p>Necessary conditions for the existence of such designs are presented. These necessary conditions will be also necessary conditions for the existence of the related $q$-Steiner system. Trivial and nontrivial direct constructions and a nontrivial recursive construction for such designs are given. Some of the designs have a symmetric structure, which is uniform in the dimensions of the existing subspaces in the system. Most constructions are based on this uniform structure of the design or its punctured designs.</p>Tuvi Etzion
Copyright (c) 2018
http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i2p8Fri, 13 Apr 2018 00:00:00 +1000