valency
Valency
2005-03-31 06:12:30
2005-04-08 14:00:51
Definition
$\rho$-valent
trivalent graph
cubic graph
regular
regular graph
graph
\usepackage{amssymb}
% \usepackage{amsmath}
% \usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% portions from
% makra.sty 1989-2005 by Marijke van Gans %
% ^ ^
\catcode`\@=11 % o o
% ->*<-
% ~
%%%% CHARS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% code char frees for
\let\Para\S % \Para § \S \scriptstyle
\let\Pilcrow\P % \Pilcrow ¶ \P
\mathchardef\pilcrow="227B
\mathchardef\lt="313C % \lt < < bra
\mathchardef\gt="313E % \gt > > ket
\let\bs\backslash % \bs \
\let\us\_ % \us _ \_ ...
\mathchardef\lt="313C % \lt < < bra
\mathchardef\gt="313E % \gt > > ket
%%%% DIACRITICS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%let\udot\d % under-dot (text mode), frees \d
\let\odot\. % over-dot (text mode), frees \.
%let\hacek\v % hacek (text mode), frees \v
%let\makron\= % makron (text mode), frees \=
%let\tilda\~ % tilde (text mode), frees \~
\let\uml\" % umlaut (text mode), frees \"
%def\ij/{i{\kern-.07em}j}
%def\trema#1{\discretionary{-}{#1}{\uml #1}}
%%%% amssymb %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\le\leqslant
\let\ge\geqslant
%let\prece\preceqslant
%let\succe\succeqslant
%%%% USEFUL MISC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\C++{C$^{_{++}}$}
%let\writelog\wlog
%def\wl@g/{{\sc wlog}}
%def\wlog{\@ifnextchar/{\wl@g}{\writelog}}
%def\org#1{\lower1.2pt\hbox{#1}}
% chem struct formulae: \bs, --- / \org{C} etc.
%%%% USEFUL INTERNAL LaTeX STUFF %%%%%%%%%%%%%%%%%%%%%%%%
%let\Ifnextchar=\@ifnextchar
%let\Ifstar=\@ifstar
%def\currsize{\@currsize}
%%%% KERNING, SPACING, BREAKING %%%%%%%%%%%%%%%%%%%%%%%%%
%def\qqquad{\hskip3em\relax}
%def\qqqquad{\hskip4em\relax}
%def\qqqqquad{\hskip5em\relax}
%def\qqqqqquad{\hskip6em\relax}
%def\qqqqqqquad{\hskip7em\relax}
%def\qqqqqqqquad{\hskip8em\relax}
%%%% LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% COUNTERS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%let\addtoreset\@addtoreset
%{A}{B} adds A to list of counters reset to 0
% when B is \refstepcounter'ed (see latex.tex)
%
%def\numbernext#1#2{\setcounter{#1}{#2}\addtocounter{#1}{\m@ne}}
%%%% EQUATIONS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% LEMMATA %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% DISPLAY %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% MATH LAYOUT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\let\D\displaystyle
\let\T\textstyle
\let\S\scriptstyle
\let\SS\scriptscriptstyle
% array:
%def\<#1:{\begin{array}{#1}}
%def\>{\end{array}}
% array using [ ] with rounded corners:
%def\[#1:{\left\lgroup\begin{array}{#1}}
%def\]{\end{array}\right\rgroup}
% array using ( ):
%def\(#1:{\left(\begin{array}{#1}}
%def\){\end{array}\right)}
%def\hh{\noalign{\vskip\doublerulesep}}
%%%% MATH SYMBOLS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\d{\mathord{\rm d}} % d as in dx
%def\e{{\rm e}} % e as in e^x
%def\Ell{\hbox{\it\char`\$}}
\def\sfmath#1{{\mathchoice%
{{\sf #1}}{{\sf #1}}{{\S\sf #1}}{{\SS\sf #1}}}}
\def\Stalkset#1{\sfmath{I\kern-.12em#1}}
\def\Bset{\Stalkset B}
\def\Nset{\Stalkset N}
\def\Rset{\Stalkset R}
\def\Hset{\Stalkset H}
\def\Fset{\Stalkset F}
\def\kset{\Stalkset k}
\def\In@set{\raise.14ex\hbox{\i}\kern-.237em\raise.43ex\hbox{\i}}
\def\Roundset#1{\sfmath{\kern.14em\In@set\kern-.4em#1}}
\def\Qset{\Roundset Q}
\def\Cset{\Roundset C}
\def\Oset{\Roundset O}
\def\Zset{\sfmath{Z\kern-.44emZ}}
% \frac overwrites LaTeX's one (use TeX \over instead)
%def\fraq#1#2{{}^{#1}\!/\!{}_{\,#2}}
\def\frac#1#2{\mathord{\mathchoice%
{\T{#1\over#2}}
{\T{#1\over#2}}
{\S{#1\over#2}}
{\SS{#1\over#2}}}}
%def\half{\frac12}
\mathcode`\<="4268 % < now is \langle, \lt is <
\mathcode`\>="5269 % > now is \rangle, \gt is >
%def\biggg#1{{\hbox{$\left#1\vbox %to20.5\p@{}\right.\n@space$}}}
%def\Biggg#1{{\hbox{$\left#1\vbox %to23.5\p@{}\right.\n@space$}}}
\let\epsi=\varepsilon
\def\omikron{o}
\def\Alpha{{\rm A}}
\def\Beta{{\rm B}}
\def\Epsilon{{\rm E}}
\def\Zeta{{\rm Z}}
\def\Eta{{\rm H}}
\def\Iota{{\rm I}}
\def\Kappa{{\rm K}}
\def\Mu{{\rm M}}
\def\Nu{{\rm N}}
\def\Omikron{{\rm O}}
\def\Rho{{\rm P}}
\def\Tau{{\rm T}}
\def\Ypsilon{{\rm Y}} % differs from \Upsilon
\def\Chi{{\rm X}}
%def\dg{^{\circ}} % degrees
%def\1{^{-1}} % inverse
\def\*#1{{\bf #1}} % boldface e.g. vector
%def\vi{\mathord{\hbox{\bf\i}}} % boldface vector \i
%def\vj{\mathord{\,\hbox{\bf\j}}} % boldface vector \j
%def\union{\mathbin\cup}
%def\isect{\mathbin\cap}
%let\so\Longrightarrow
%let\oso\Longleftrightarrow
%let\os\Longleftarrow
% := and :<=>
%def\isdef{\mathrel{\smash{\stackrel{\SS\rm def}{=}}}}
%def\iffdef{\mathrel{\smash{stackrel{\SS\rm def}{\oso}}}}
\def\isdef{\mathrel{\mathop{=}\limits^{\smash{\hbox{\tiny def}}}}}
%def\iffdef{\mathrel{\mathop{\oso}\limits^{\smash{\hbox{\tiny %def}}}}}
%def\tr{\mathop{\rm tr}} % tr[ace]
%def\ter#1{\mathop{^#1\rm ter}} % k-ter[minant]
%let\.=\cdot
%let\x=\times % ÃÂ (direct product)
%def\qed{ ${\S\circ}\!{}^\circ\!{\S\circ}$}
%def\qed{\vrule height 6pt width 6pt depth 0pt}
%def\edots{\mathinner{\mkern1mu
% \raise7pt\vbox{\kern7pt\hbox{.}}\mkern1mu % .shorter
% \raise4pt\hbox{.}\mkern1mu % .
% \raise1pt\hbox{.}\mkern1mu}} % .
%def\fdots{\mathinner{\mkern1mu
% \raise7pt\vbox{\kern7pt\hbox{.}} % . ~45°
% \raise4pt\hbox{.} % .
% \raise1pt\hbox{.}\mkern1mu}} % .
\def\mod#1{\allowbreak \mkern 10mu({\rm mod}\,\,#1)}
% redefines TeX's one using less space
%def\int{\intop\displaylimits}
%def\oint{\ointop\displaylimits}
%def\intoi{\int_0^1}
%def\intall{\int_{-\infty}^\infty}
%def\su#1{\mathop{\sum\raise0.7pt\hbox{$\S\!\!\!\!\!#1\,$}}}
%let\frakR\Re
%let\frakI\Im
%def\Re{\mathop{\rm Re}\nolimits}
%def\Im{\mathop{\rm Im}\nolimits}
%def\conj#1{\overline{#1\vphantom1}}
%def\cj#1{\overline{#1\vphantom+}}
%def\forAll{\mathop\forall\limits}
%def\Exists{\mathop\exists\limits}
%%%% PICTURES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\cent{\makebox(0,0)}
%def\node{\circle*4}
%def\nOde{\circle4}
%%%% REFERENCES %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\opcit{[{\it op.\,cit.}]}
\def\bitem#1{\bibitem[#1]{#1}}
\def\name#1{{\sc #1}}
\def\book#1{{\sl #1\/}}
\def\paper#1{``#1''}
\def\mag#1{{\it #1\/}}
\def\vol#1{{\bf #1}}
\def\isbn#1{{\small\tt ISBN\,\,#1}}
\def\seq#1{{\small\tt #1}}
%def\url<{\verb>}
%def\@cite#1#2{[{#1\if@tempswa\ #2\fi}]}
%%%% VERBATIM CODE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%def\"{\verb"}
%%%% AD HOC %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% WORDS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \hyphenation{pre-sent pre-sents pre-sent-ed pre-sent-ing
% re-pre-sent re-pre-sents re-pre-sent-ed re-pre-sent-ing
% re-fer-ence re-fer-ences re-fer-enced re-fer-encing
% ge-o-met-ry re-la-ti-vi-ty Gauss-ian Gauss-ians
% Des-ar-gues-ian}
%def\oord/{o{\trema o}rdin\-ate}
% usage: C\oord/s, c\oord/.
% output: co\"ord... except when linebreak at co-ord...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ^ ^
\catcode`\@=12 % ` '
% ->*<-
% ~
\PMlinkescapeword{cyclic}
\PMlinkescapeword{scope}
\PMlinkescapeword{structures}
In a graph, multigraph, or pseudograph $G$, the {\bf valency} of a vertex is
the number of edges attached to it (note that a loop counts twice).
Synonymous with {\bf \PMlinkescapetext{valence}} and
{\bf \PMlinkescapetext{degree}}. There are some unrelated things also
called valence; there are of course many things all called degree.
For directed graphs, {\bf in-} and {\bf out-} are prefixed to any of the synonyms, to count incoming and outgoing edges separately.
If $\rho(\hbox{\sc v})$ is used for the valency of vertex $\hbox{\sc v}$, the notation $\rho(G)$ (or $\rho$ on its own if there is no scope for confusion) denotes the maximum valency found in graph $G$. Another notation often seen is $\delta(G)$ and $\Delta(G)$ for lowest and highest valency in $G$ respectively.
If the valency is the same number ($\rho$, say) for all its vertices, $G$ is called {\bf regular}. More specifically it is called {\bf $\rho$-valent} or $\rho$-regular. Connected (components of)\dots
%
\begin{itemize}
\item \dots0-valent graphs are edgeless vertices,
\item \dots1-valent graphs are pairs of vertices joined by an edge,
\item \dots2-valent graphs are cyclic graphs, i.e.\ $n$-gons, of various sizes
\item From $\rho\ge3$ these structures start getting more interesting.
3-valent (or {\bf trivalent}) graphs are also known as
{\bf cubic graphs}.
\end{itemize}
A $\rho$-valent graph with $n$ vertices has $n\,\rho/2$ edges.