Hamiltonian cycles in cubic Cayley graphs: the 〈2,4k,3〉 case

It was proved by Glover and Maru?i? (J. Eur. Math. Soc. 9:775–787, 2007), that cubic Cayley graphs arising from groups G=〈a,x∣a ²=x ^s =(ax)³=1,…〉 having a (2,s,3)-presentation, that is, from groups generated by an involution a and an element x of order s such that their product ax has order 3, have a Hamiltonian cycle when |G| (and thus also s) is congruent to 2 modulo 4, and have a Hamiltonian path when |G| is congruent to 0 modulo 4. In this article the existence of a Hamiltonian cycle is proved when apart from |G| also s is congruent to 0 modulo 4, thus leaving |G| congruent to 0 modulo 4 with s either odd or congruent to 2 modulo 4 as the only remaining cases to be dealt with in order to establish existence of Hamiltonian cycles for this particular class of cubic Cayley graphs.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

Class Ⅰ graphs of nonnegative characteristic without special cycles

In this paper,we prove that every graph with maximum degree six that can be embedded in a surface of nonnegative characteristic is of Class Ⅰ if it does not contain a 5- or 6-cycle with a chord,which e...     

Which distance-hereditary graphs are cover–incomparability graphs?

In this paper we deal with cover–incomparability graphs of posets, or briefly C–I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C–I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C–I graphs? It follows that C–I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C–I graphs in general is known to be NP-complete.     

A Ramsey–Turán theory for tilings in graphs

For a $k$-vertex graph $F$ and an $n$-vertex graph $G$, an $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$. For $r\in \mathbb{N}$, the $r$-independence number of $G$, denoted ${\alpha }_r(G)$, is the largest size of a $K_r$-free set of vertices in $G$. In this article, we discuss Ramsey–Turán-type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal $F$-tilings. Our results unify and generalise previous results of Balogh–Molla–Sharifzadeh [Random Struct. Algoritm. 49 (2016), no. 4, 669–693], Nenadov–Pehova [SIAM J. Discret. Math. 34 (2020), no. 2, 1001–1010] and Balogh–McDowell–Molla–Mycroft [Comb. Probab. Comput. 27 (2018), no. 4, 449–474] on the subject.     

Acyclic edge coloring of planar graphs without cycles of?specific lengths

A proper edge coloring of a graph G is called acyclic edge coloring if there are no bicolored cycles in G. Let ??(G) denote the maximum degree of G. In this paper, we prove that every planar graph with ??(G)??10 and without cycles of lengths 4 to 11 is acyclic (??(G)+1)-edge colorable, and every planar graph with ??(G)??11 and without cycles of lengths 4 to 9 is acyclic (??(G)+1)-edge colorable.     

The Birman–Craggs–Johnson homomorphism and abelian cycles in the Torelli group

In the 1970s, Birman–Craggs–Johnson (BCJ) (Trans AMS 237: 283–309, 1978; Trans AMS 261(1):423–422, 1980) used Rochlin’s invariant for homology 3-spheres to construct a remarkable surjective homomorphism , where is the Torelli group and B ₃ is a certain -vector space of Boolean (square-free) polynomials. By pulling back cohomology classes and evaluating them on abelian cycles, we construct dimensions worth of nontrivial elements of which cannot be detected rationally. These classes in fact restrict to nontrivial classes in the cohomology of the subgroup generated by Dehn twists about separating curves. We also use the “Casson–Morita algebra” and Morita’s integral lift of the BCJ map restricted to to give the same lower bound on . The first author is partially supported by NSF grant DMS-0606882 and was also supported in part by NSF grant DMS-0504208 and by a VIGRE postdoc under NSF grant 9983660 to Cornell University. The second author is supported in part by NSF grant DMS-0244542.     

Lovász–Schrijver SDP-operator,near-perfect graphs and near-bipartite graphs

We study the Lovász–Schrijver lift-and-project operator (\({{\mathrm{\text {LS}}}}_+\)) based on the cone of symmetric, positive semidefinite matrices, applied to the fractional stable set polytope of graphs. The problem of obtaining a combinatorial characterization of graphs for which the \({{\mathrm{\text {LS}}}}_+\)-operator generates the stable set polytope in one step has been open since 1990. We call these graphs \({{{\mathrm{\text {LS}}}}}_+\)-perfect. In the current contribution, we pursue a full combinatorial characterization of \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs and make progress towards such a characterization by establishing a new, close relationship among \({{{\mathrm{\text {LS}}}}}_+\)-perfect graphs, near-bipartite graphs and a newly introduced concept of full-support-perfect graphs.     

Robust cycles in Kolmogorov–Lotka–Volterra class of models with intraspecific co-operation

Using the Andronov–Hopf bifurcation theorem and the Poincaré–Bendixson Theorem, we explore robust cyclical possibilities in Kolmogorov–Lotka–Volterra class of models with positive intraspecific cooperation (in the form of social networks) in the prey population. We find that this additional feedback effect of intraspecific cooperation introduces nonlinearities which modify the cyclical outcomes of the model. We show that the cyclical outcomes are more robust than in the existing literature in this area due to introduction of such non-linearities. We also demonstrate the possibilities of multiple limit cycles under certain situations.     

Chip-firing based methods in the Riemann–Roch theory of directed graphs

Baker and Norine proved a Riemann–Roch theorem for divisors on undirected graphs. The notions of graph divisor theory are in duality with the notions of the chip-firing game of Björner, Lovász and Shor. We use this connection to prove Riemann–Roch-type results on directed graphs. We give a simple proof for a Riemann–Roch inequality on Eulerian directed graphs, improving a result of Amini and Manjunath. We also study possibilities and impossibilities of Riemann–Roch-type equalities in strongly connected digraphs and give examples. We intend to make the connections of this theory to graph theoretic notions more explicit via using the chip-firing framework.     

On maximum matchings in König–Egerváry graphs

For a graph $G$ let $\alpha \left(G\right),\mu \left(G\right)$, and $\tau \left(G\right)$ denote its independence number, matching number, and vertex cover number, respectively. If $\alpha \left(G\right)+\mu \left(G\right)=\left|V\left(G\right)\right|$ or, equivalently, $\mu \left(G\right)=\tau \left(G\right)$, then $G$ is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs.     

Distance–regular graphs having the M-property

We analyse when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is an M-matrix; that is, it has non-positive off-diagonal elements or, equivalently when the Moore–Penrose inverse of the combinatorial Laplacian of a distance–regular graph is also the combinatorial Laplacian of another network. When this occurs we say that the distance–regular graph has the M-property. We prove that only distance–regular graphs with diameter up to three can have the M-property and we give a characterization of the graphs that satisfy the M-property in terms of their intersection array. Moreover, we exhaustively analyse strongly regular graphs having the M-property and we give some families of distance–regular graphs with diameter three that satisfy the M-property. Roughly speaking, we prove that all distance–regular graphs with diameter one; about half of the strongly regular graphs; only some imprimitive distance–regular graphs with diameter three, and no distance–regular graphs with diameter greater than three, have the M-property. In addition, we conjecture that no primitive distance–regular graph with diameter three has the M-property.     

The odd–even invariant for graphs

The odd–even invariant for graphs is the graphic version of the odd–even invariant for oriented matroids. Here, simple properties of this invariant are verified, and for certain graphs, including chordal graphs and complete bipartite graphs, its value is determined. The odd–even chromatic polynomial is introduced, its coefficients are briefly studied, and it is shown that the absolute value of this polynomial at −1 equals the odd–even invariant, in analogy with the usual chromatic polynomial and the number of acyclic orientations.     

Euclidean realizations of Mauldin–Williams graphs

“Graph-directed” fractals are collections of metric spaces, each of which can be expressed as a union of several scaled copies of spaces from the collection. They give rise to weighted, directed graphs where the term comes from. We show in this note that any (finite) weighted, directed graph (with weights between 0 and 1) can be realized in a Euclidean space in the sense that, starting from the graph one can define a system of similitudes (with the similarity ratios being the given weights) on an appropriate Euclidean space. The point is that these maps satisfy a certain property (called the open set condition) so that the theory of Mauldin–Williams can be applied to compute the dimension of the emerging fractals. Additionally, we give a novel example of a system of graph-directed fractals.