Search Results
You are looking at 1 - 5 of 5 items for
- Author or Editor: G. Chartrand x
- Refine by Access: All Content x
Conditions on a graphG are presented which are sufficient to guarantee thatG−Z contains a 1-factor, whereZ is a set of edges ofG of restricted cardinality. These conditions provide generalizations of several known results and, further, establish the result that ifG is anr-regular, (r−2)-edge-connected graph (r≥2) of even order andz is an integer with 0≤z≤r−1 such thatG contains fewer thanr−z edge cut sets of cardinalityr−2, thenG−Z has a 1-factor for each setZ ofz edges ofG.
A graphH divides a graphG, writtenH|G, ifG isH-decomposable. A graphG without isolated vertices is a greatest common divisor of two graphsG 1 andG 2 ifG is a graph of maximum size for whichG|G 1 andG|G 2, while a graphH without isolated vertices is a least common multiple ofG 1 andG 2 ifH is a graph of minimum size for whichG 1|H andG 2|H. It is shown that every two nonempty graphs have a greatest common divisor and least common multiple. It is also shown that the ratio of the product of the sizes of a greatest common divisor and least common multiple ofG 1 andG 2 to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG 1,G 2 of graphs are determined, including when one ofG 1 andG 2 is a cycle of even length and the other is a star.
For a graphG, the switched graphS
v
(G) ofG at a vertexv is the graph obtained fromG by deleting the edges ofG incident withv and adding the edges of
incident withv. Properties of graphs whereS
v
(G) ≅G or
are studied. This concept is extended to the partial complementS
H
(G) where H
. The investigation here centers around the existence of setsH for whichS
H
(G) ≅ G. A parameter is introduced which measures how near a graph is to being self-complementary.
