共查询到20条相似文献,搜索用时 0 毫秒
1.
Henry H. Glover Klavdija Kutnar Dragan Marušič 《Journal of Algebraic Combinatorics》2009,30(4):447-475
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 2=x s =(ax)3=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. 相似文献
2.
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 CNPq (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01. 相似文献
3.
4.
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... 相似文献
5.
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. 相似文献
6.
7.
8.
9.
Jie Han Patrick Morris Guanghui Wang Donglei Yang 《Random Structures and Algorithms》2024,64(1):94-124
For a -vertex graph and an -vertex graph , an -tiling in is a collection of vertex-disjoint copies of in . For , the -independence number of , denoted , is the largest size of a -free set of vertices in . 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 -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. 相似文献
10.
11.
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. 相似文献
12.
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
3 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. 相似文献
13.
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. 相似文献
14.
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. 相似文献
15.
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. 相似文献
16.
17.
For a graph let , and denote its independence number, matching number, and vertex cover number, respectively. If or, equivalently, , then is a König–Egerváry graph.In this paper we give a new characterization of König–Egerváry graphs. 相似文献
18.
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. 相似文献
19.
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. 相似文献
20.
“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. 相似文献