# 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 graphsG1 andG2 ifG is a graph of maximum size for whichG|G1 andG|G2, while a graphH without isolated vertices is a least common multiple ofG1 andG2 ifH is a graph of minimum size for whichG1|H andG2|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 ofG1 andG2 to the product of their sizes can be arbitrarily large or arbitrarily small. Sizes of least common multiples of various pairsG1,G2 of graphs are determined, including when one ofG1 andG2 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 graphSv(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 whereSv(G)G or are studied. This concept is extended to the partial complementSH(G) where H . The investigation here centers around the existence of setsH for whichSH(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