𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Parity results on connected ƒ-factors

✍ Scribed by Kenneth A. Berman

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
531 KB
Volume
59
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a connected graph with vertex set V and let d(v) denote the degree of a vertex v ~ V. For f a mapping from V to the positive integers, an f-factor is a spanning subgraph having degree f(v) at vertex v. In this paper we extend the parity results of Thomason [2] on Hamiltonian circuits to connected f-factors. (A Hamiltonian circuit is a connected 2-factor.) We show that if f(v) and d(v) have opposite parity for all v ~ V then for any given subgraph C there is an even number of connected f-factors having C as a cotree.

Let [1 and fz be any mappings from V to the positive integers that partition d, i.e., d(v) =fx(v)+f2(v) for all v ~ V. Let C: and C 2 be any pair of edge disjoint subgraphs. We also show in this paper that the number of decompositions of G into a connected fl-factor having C 1 as a cotree and a connected/e-factor having Ce as a cotree is even.

📜 SIMILAR VOLUMES

Connected (g, f)-factors
Connected (g, f)-factors
✍ M. N. Ellingham; Yunsun Nam; Heinz-Jürgen Voss 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

## Abstract In this paper we study connected (__g, f__)‐factors. We describe an algorithm to connect together an arbitrary spanning subgraph of a graph, without increasing the vertex degrees too much; if the algorithm fails we obtain information regarding the structure of the graph. As a consequenc

Connectivity on Complete Lattices: New R
Connectivity on Complete Lattices: New Results
✍ Ulisses Braga-Neto; John Goutsias 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 451 KB

The notion of connectivity is very important in image processing and analysis, and particularly in problems related to image segmentation. It is well understood, however, that classical notions of connectivity, including topological and graph-theoretic notions, are not compatible with each other. Th

On factors of 4-connected claw-free grap
On factors of 4-connected claw-free graphs
✍ H. J. Broersma; M. Kriesell; Z. Ryjác̆ek 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

## Abstract We consider the existence of several different kinds of factors in 4‐connected claw‐free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4‐connected line graph is hamiltonian,

On the Parity of Exponents in the Factor
On the Parity of Exponents in the Factorization ofn!
✍ Daniel Berend 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 264 KB

It is shown that, for any k, there exist infinitely many positive integers n such that in the prime power factorization of n!, all first k primes appear to even exponents. This answers a question of Erdo s and Graham (``Old and New Problems and Results in Combinatorial Number Theory,'' L'Enseignemen

On the Parity of Exponents in the Prime
On the Parity of Exponents in the Prime Factorization of Factorials
✍ J.W. Sander 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 126 KB

In 1997 Berend proved a conjecture of Erdo s and Graham by showing that for every positive integer r there are infinitely many positive integers n with the property that where p(1)=2, p(2)=3, p(3)=5, ... is the sequence of primes in ascending order, and e p (m) denotes the order of the prime p in t