Journal of the
Korean Mathematical Society
JKMS

ISSN(Print) 0304-9914 ISSN(Online) 2234-3008

Article

HOME ALL ARTICLES View

J. Korean Math. Soc. 2008; 45(6): 1613-1622

Printed November 1, 2008

Copyright © The Korean Mathematical Society.

Randomly orthogonal factorizations of $(0,mf-(m-1)r)$-graphs

Sizhong Zhou and Minggang Zong

Jiangsu University of Science and Technology and Jiangsu University

Abstract

Let $G$ be a graph with vertex set $V(G)$ and edge set $E(G)$, and let $g,f$ be two nonnegative integer-valued functions defined on $V(G)$ such that $g(x)\leq f(x)$ for every vertex $x$ of $V(G)$. We use $d_G(x)$ to denote the degree of a vertex $x$ of $G$. A $(g,f)$-factor of $G$ is a spanning subgraph $F$ of $G$ such that $g(x)\leq d_F(x)\leq f(x)$ for every vertex $x$ of $V(F)$. In particular, $G$ is called a $(g,f)$-graph if $G$ itself is a $(g,f)$-factor. A $(g,f)$-factorization of $G$ is a partition of $E(G)$ into edge-disjoint $(g,f)$-factors. Let $F=\{F_1,F_2,\ldots,F_m\}$ be a factorization of $G$ and $H$ be a subgraph of $G$ with $mr$ edges. If $F_i,1\leq i\leq m,$ has exactly $r$ edges in common with $H$, we say that $F$ is $r$-orthogonal to $H$. If for any partition $\{A_1,A_2,\ldots,A_m\}$ of $E(H)$ with $|A_i|=r$ there is a $(g,f)$-factorization $F=\{F_1,F_2,\ldots,F_m\}$ of $G$ such that $A_i\subseteq E(F_i)$, $1\leq i\leq m$, then we say that $G$ has $(g,f)$-factorizations randomly $r$-orthogonal to $H$. In this paper it is proved that every $(0,mf-(m-1)r)$-graph has $(0,f)$-factorizations randomly $r$-orthogonal to any given subgraph with $mr$ edges if $f(x)\geq 3r-1$ for any $x\in V(G)$.

Keywords: graph, subgraph, factor, orthogonal factorization

MSC numbers: 05C70