# Search Results

## You are looking at 1 - 5 of 5 items for

• Author or Editor: G. Chartrand
• Refine by Access: All Content
Clear All Modify Search

# A note on 1-factors in graphs

Periodica Mathematica Hungarica
Authors: G. Chartrand and L. Nebeský

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≤zr−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.

Restricted access

# Graphs with prescribed degree sets and girth

Periodica Mathematica Hungarica
Authors: G. Chartrand, R. Gould, and S. Kapoor
Restricted access

# Greatest common divisors and least common multiples of graphs

Periodica Mathematica Hungarica
Authors: G. Chartrand, L. Holley, G. Kubicki, and M. Schultz

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.

Restricted access

# The partial complement of graphs

Periodica Mathematica Hungarica
Authors: G. Chartrand, S. F. Kapoor, D. R. Lick, and S. Schuster

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.

Restricted access

# Variations on a theorem of Petersen

Periodica Mathematica Hungarica
Authors: K. S. Bagga, L. W. Beineke, G. Chartrand, and O. R. Oellermann
For an (r − 2)-edge-connected graphG (r ≥ 3) for orderp containing at mostk edge cut sets of cardinalityr − 2 and for an integerl with 0 ≤l ≤ ⌊p/2⌋, it is shown that (1) ifp is even, 0 ≤k ≤ r(l + 1) − 1, and
\documentclass{aastex} \usepackage{amsbsy} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{bm} \usepackage{mathrsfs} \usepackage{pifont} \usepackage{stmaryrd} \usepackage{textcomp} \usepackage{upgreek} \usepackage{portland,xspace} \usepackage{amsmath,amsxtra} \pagestyle{empty} \DeclareMathSizes{10}{9}{7}{6} \begin{document} $$\mathop \sum \limits_{v \in V(G)} |\deg _G v - r|< r(2 + 2l) - 2k$$ \end{document}
, then the edge independence numberβ1(G) is at least (p − 2l)/2, and (2) ifp is odd, The sharpness of these results is discussed.
Restricted access