Vertex-magic labelings of regular graphs II

Previously the first author has shown how to construct vertex-magic total labelings (VMTLs) for large families of regular graphs. The construction proceeds by successively adding arbitrary 2-factors to a regular graph of order n which possesses a strong VMTL, to produce a regular graph of the same order but larger size. In this paper, we exploit this construction method. We are able to show that for any r≥4, every r-regular graph of odd order n≤17 has a strong VMTL. We show how to produce strong labelings for some families of 2-regular graphs since these are used as the starting points of our construction. While even-order regular graphs are much harder to deal with, we introduce ‘mirror’ labelings which provide a suitable starting point from which the construction can proceed. We are able to show that several large classes of r-regular graphs of even order (including some Hamiltonian graphs) have VMTLs.     

Labeling constructions using digraph products

In this paper we study the edge-magicness of graphs with equal size and order, and we use such graphs and digraph products in order to construct labelings of different classes and of different graphs. We also study super edge-magic labelings of 2$2$-regular graphs with exactly two components and their implications to other labelings.     

Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.     

图P_n~2的-优美性

本文针对［１］中提出的猜测“我们猜测Ｐｎ２是优美的,尽管标号看来更复杂”,对Ｐｎ２的标号作了一些工作,证明了Ｐｎ２：是－优美的．     

On sequential labelings of graphs

A valuation on a simple graph G is an assignment of labels to the vertices of G which induces an assignment of labels to the edges of G. β-valuations, also called graceful labelings, and α-valuations, a subclass of graceful labelings, have an extensive literature; harmonious labelings have been introduced recently by Graham and Sloane. This paper introduces sequential labelings, a subclass of harmonious labelings, and shows that any tree admitting an α-valuation also admits a sequential labeling and hence is harmonious. Constructions are given for new families of graceful and sequential graphs, generalizing some earlier results. Finally, a conjecture of Frucht is shown to be wrong by exhibiting several graceful labelings of wheels in which the center label is larger than previously thought possible.     

Decomposition of cubic graphs with a 2-factor consisting of three cycles

The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles.     

A Note on 5-Cycle Double Covers

The strong cycle double cover conjecture states that for every circuit C of a bridgeless cubic graph G, there is a cycle double cover of G which contains C. We conjecture that there is even a 5-cycle double cover S of G which contains C, i.e. C is a subgraph of one of the five 2-regular subgraphs of S. We prove a necessary and sufficient condition for a 2-regular subgraph to be contained in a 5-cycle double cover of G.     

Antimagic orientations of even regular graphs

A labeling of a digraph D with m arcs is a bijection from the set of arcs of D to . A labeling of D is antimagic if no two vertices in D have the same vertex-sum, where the vertex-sum of a vertex for a labeling is the sum of labels of all arcs entering u minus the sum of labels of all arcs leaving u. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, Mütze, and Schwartz [On antimagic directed graphs, J. Graph Theory 64 (2010) 219–232] initiated the study of antimagic labelings of digraphs, and conjectured that every connected graph admits an antimagic orientation, where an orientation D of a graph G is antimagic if D has an antimagic labeling. It remained unknown whether every disjoint union of cycles admits an antimagic orientation. In this article, we first answer this question in the positive by proving that every 2-regular graph has an antimagic orientation. We then show that for any integer , every connected, 2d-regular graph has an antimagic orientation. Our technique is new.     

Hamilton decompositions of some line graphs

The main result of this paper completely settles Bermond's conjecture for bipartite graphs of odd degree by proving that if G is a bipartite (2k + 1)-regular graph that is Hamilton decomposable, then the line graph, L(G), of G is also Hamilton decomposable. A similar result is obtained for 5-regular graphs, thus providing further evidence to support Bermond's conjecture. © 1995 John Wiley & Sons, Inc.     

A note on minimum graphs with girth pair (4, 2l + 1)

We show that the size of a smallest connected k-regular graph with girth pair (4, 2l + 1) is within a constant of (2l + 1) k/2. In so doing we disprove a conjecture of Harary and Kovacs.     

On the distribution of range for tree-indexed random walks

We study tree-indexed random walks as introduced by Benjamini, Häggström, and Mossel, i.e., labelings of a tree for which adjacent vertices have labels differing by 1. It is a conjecture of those authors that the distribution of the range for any such tree is dominated by that of a path on the same number of edges. The two main variants of this conjecture considered in the literature are the standard walks, in which adjacent vertices must have labels differing by exactly 1, and lazy walks, in which adjacent vertices must have labels differing by at most 1. We confirm this conjecture for all trees in the lazy case and provide some partial results in the standard case.     

On a conjecture of Graham and Häggkvist with the polynomial method

A conjecture of Graham and Häggkvist states that every tree with m edges decomposes every 2m-regular graph and every bipartite m-regular graph. Let T be a tree with a prime number p of edges. We show that if the growth ratio of T at some vertex v₀ satisfies ρ(T,v₀)≥^1/2, where is the golden ratio, then T decomposes K_2p,2p. We also prove that if T has at least p/3 leaves then it decomposes K_2p,2p. This improves previous results by Häggkvist and by Lladó and López. The results follow from an application of Alon’s Combinatorial Nullstellensatz to obtain bigraceful labelings.     

Hermitian <Emphasis Type="Italic">K</Emphasis>-theory and 2-regularity for totally real number fields

We completely determine the 2-primary torsion subgroups of the hermitian K-groups of rings of 2-integers in totally real 2-regular number fields. The result is almost periodic with period 8. Moreover, the 2-regular case is precisely the class of totally real number fields that have homotopy cartesian “Bökstedt square”, relating the K-theory of the 2-integers to that of the fields of real and complex numbers and finite fields. We also identify the homotopy fibers of the forgetful and hyperbolic maps relating hermitian and algebraic K-theory. The result is then exactly periodic of period 8 in the orthogonal case. In both the orthogonal and symplectic cases, we prove a 2-primary hermitian homotopy limit conjecture for these rings.     

Hamiltonian decomposition of Cayley graphs of ordersp 2 andpq

In this paper, it is proved that any connected Cayley graph on an abelian group of order pq orp ² has a hamiltonian decomposition, wherep andq are odd primes. This result answers partially a conjecture of Alspach concerning hamiltonian decomposition of 2k-regular connected Cayley graphs on abelian groups.     

Maximum Genus of Strong Embeddings

The strong embedding conjecture states that any 2-connected graph has a strong embedding on some surface. It implies the circuit double cover conjecture: Any 2-connected graph has a circuit double cover.Conversely, it is not true. But for a 3-regular graph, the two conjectures are equivalent. In this paper, a characterization of graphs having a strong embedding with exactly 3 faces, which is the strong embedding of maximum genus, is given. In addition, some graphs with the property are provided. More generally, an upper bound of the maximum genus of strong embeddings of a graph is presented too. Lastly, it is shown that the interpolation theorem is true to planar Halin graph.     

6-regular Cayley graphs on abelian groups of odd order are hamiltonian decomposable

Alspach conjectured that any 2k-regular connected Cayley graph on a finite abelian group A has a hamiltonian decomposition. In this paper, the conjecture is shown true if k=3, and the order of A is odd.     

A note on Hamiltonian decompositions of Cayley graphs

We define a class Γ of 4-regular Cayley graphs on abelian groups and prove every element of Γ to be decomposable into two Hamiltonian cycles. This result is a special case of a conjecture ofB. Alspach and includes a theorem ofJ.-C. Bermond et al. as a subcase.     

Equations resolving a conjecture of Rado on partition regularity

A linear equation L is called k-regular if every k-coloring of the positive integers contains a monochromatic solution to L. Richard Rado conjectured that for every positive integer k, there exists a linear equation that is (k−1)-regular but not k-regular. We prove this conjecture by showing that the equation has this property.This conjecture is part of problem E14 in Richard K. Guy's book “Unsolved Problems in Number Theory”, where it is attributed to Rado's 1933 thesis, “Studien zur Kombinatorik”.     

Three-regular subgraphs of four-regular graphs

Berge conjectured that every finite simple 4-regular graph G contains a 3-regular subgraph. We prove that this conjecture is true if the cyclic edge connectivity λ^c(G) of G is at least 10. Also we prove that if G is a smallest counterexample, then λ^c(G) is either 6 or 8.     

A conjecture on strong magic labelings of 2-regular graphs

Let sC₃ denote the disjoint union of s copies of C₃. For each integer t≥2 it is shown that the disjoint union C₅∪(2t)C₃ has a strong vertex-magic total labeling (and therefore it must also have a strong edge-magic total labeling). For each integer t≥3 it is shown that the disjoint union C₄∪(2t−1)C₃ has a strong vertex-magic total labeling. These results clarify a conjecture on the magic labeling of 2-regular graphs, which posited that no such labelings existed. It is also shown that for each integer t≥1 the disjoint union C₇∪(2t)C₃ has a strong vertex-magic total labeling. The construction employs a technique of shifting rows of (newly constructed) Kotzig arrays to label copies of C₃. The results add further weight to a conjecture of MacDougall regarding the existence of vertex-magic total labeling for regular graphs.