数理解析研究所講究録
第 671 巻 1988 年 116-125$1A\tilde{\neg}$2-MULTIGRAPHS
Richard A. Brualdi
Department of Mathematics
University of Wisconsin
Madison, WI 53706 USA

This lecture is based on the two papers [1] and [2] written jointly with T. S. Michael. We
refer to these articles for the references not provided here.
Let$G=$(V,E) be a$u\sim t$

可 raph.

Thus V $=\{1,2,\ldots,n\}$ is a set ofis a multiset of unordered pairs of distinct vertices calledoccurs at most twice in(1)$E$$ed-\underline{\alpha es}$

. In a$n$

vertices and E4$2- multi_{\underline{ff}1}\cdot aph$each edge, equivalently at most two edges join each pair of distinct vertices.

$\underline{Exam_{-}\mathfrak{v}1e}$Let$d_{i}$$d_{4}=3,$equal the number of edges that meet vertex$d_{5}=3$ ,and

$d_{6}=2$. The degree$\underline{seo_{-}uence}$$i$. Then$d_{1}=4$ ,$d_{2}=4$ ,$d_{3}=4$ ,is (4,4,4,3,3,2).

With proper labelling of the vertices we may always assume that the degree sequence$D=(d_{1}, \ldots,d_{n})$of a multigraph satisfies$d_{1}\geq\cdots\geq d_{n}$. This assumption is made implicitly

throughout.

Our object of study is the classsequence$D=(d_{1}, \ldots,d_{n})$$\mathfrak{G}_{2}(D)$of all2-multigraphs with the same degree. The frst question that arises is that of the nonemptiness of thisclass.

I.
$\triangleleft\cdot A\backslash \gamma_{-\neg}’$(2)$\underline{Theorem}$$D=(d_{1}, \ldots,d_{n})$(3)(4)(Chungphaisan 1974).

if

There exists -a2-multigraph$\underline{with}$degree se uence$\underline{and}\underline{onlv}\mathscr{Q}$$d_{1}+-+d_{n}\llcorner s\underline{even}$,$\sum^{k}d_{i}\leq 2k(k-1)+\sum^{n}$$(k=1, \ldots,n)$$\min\{2k,d_{i}\}$.

$i=k+1$$i=1$

The above is a special case of a more general theorem of Chungphaisan for r-multigraphs
obtained by replacing the three $2’ s$ above by$r’ s$. The case$r=1$

is then the following wellknow result.

(5)

Theorem(Erd\"os/Gallai1960).

$\underline{There}$$\underline{exists}$

a$g\llcorner apk$$\underline{with}$degree$\ovalbox{\tt\small REJECT} se$$D=(d_{1}, \ldots,d_{n})\underline{if}\underline{and}\underline{onlv}\underline{if}$,(6)$d_{1}+\cdots+d_{n}\underline{is}\underline{even}$(7)$\sum_{i=1}^{k}d_{i}\leq k(k-1)+\sum_{i=k+1}^{n}\min\{k,d_{i}\}$$(k=1, \ldots,n)$.

We now adopt the following color convention for 2-multigraphs. An edge of multiplicity2is denoted by one blue

denoted by one$xe\Delta\underline{e}\ovalbox{\tt\small REJECT}\underline{e}$$gdA_{rightarrow}^{e}$(designated by a bold edge).

An edge of multiplicity 1 is:$=_{j}1$$\ovalbox{\tt\small REJECT}_{j}1$2:$\frac{blue}{1}j$:$\frac{red}{1}$ .

$A^{=}\backslash \#rightarrow\prime P$2-multigraph is a graph in which every edge is colored red or blue, where red

Thus acounts as 1 and blue counts as 2.

(8)

le. Two 2-multigraphs with the degree sequence$\underline{Exam_{-}o}$$D=$(4,4,4,4,4,):The example on the right is parsimonious in the sense that it has the smallest number ofcolored edges among all 2-multigraphs in
Let

$G$

be a 2-multigraph in$\mathfrak{G}_{2}(D)$$\mathfrak{G}_{2}(D)$. Then$\beta(G)=$number of blue edges of$\rho(G)=$number of red edges of$\tau(G)=$number of colored edges of$m(G)=$ number of edges of$G$

It follows that(9)$\tau(G)=\beta(G)+\rho(G)$ ,(10)$m(G)=(d_{1}+\cdots+d_{n})/2$.

$=2\beta(G)+\rho(G)$$=\tau(G)+\beta(G)$$=2\tau(G)-p(G)$ .

3

$G$

$G$,,
$G$

,

counting multiplicites.

}$C^{\backslash }$$\gamma A$のThe 2-multigraphmultigraphs

$H$

$G$

-oarsimonions provided

is calledwith the same degree sequence

the following is equivalent to the parsimony of(11)$\underline{Exam_{-}n1e}$.

$G$

$D$

$\leq$$\tau(H)$for all2-as G. It follows from (10) that each of:$\beta(G)\geq\beta(H)$for all$H\in \mathfrak{G}_{2}(D)$$\rho(G)\leq p(H)$for all$H\in \mathfrak{G}_{2}(D)$The following two$\tau(G)$,.

2-multigraphs with degree sequence(3,3,2,1,1)

are$parsmonous:\ovalbox{\tt\small REJECT}\ovalbox{\tt\small REJECT}$The red$L^{ra}4^{\underline{h}}$of a 2-multigraph is the graph (not the 2-multigraph) determined by its

red edges with isolated vertices deleted.

(12) Theorem.

i\S$\underline{either}g\underline{star}$$\underline{Each}\underline{connected}\underline{com_{-}Donent}$$(\underline{a} K_{1,t} \underline{for}\underline{some} t\geq 1)$

onent is aconnected $\underline{com_{-}D}$(13)$\ovalbox{\tt\small REJECT} m$$\underline{trian}-\alpha le$of$\underline{the}\underline{red}$$gr\underline{a}$grap-le$\underline{triana}$$\underline{h}\underline{of}\underline{a}\underline{oarsimonious}- 2- multi\underline{\not\subset}ra_{-}Dh$$(\underline{a} K_{3})$.

$\underline{Furthermore}\underline{at}\underline{most}\underline{o}ng$.

. The converse of Theorem (12) does not hold. The 2-multigraphキ/,$\backslash$$\lambda$$_{4}8:$:$\lambda_{t})\dagger_{i}$with degree sequence$D=$(2,2,1,1,1,1) has a red graph consisting of two stars

the 2-multigraph with degree sequenceI$K_{1,2}$, but

$D$

$[$

一一

has fewer colored edges.
A$\Omega^{a}a\Delta X$

is a graph each of whose connected components is a star or a triangle with at

most one component equal to a triangle. A stellar $galaAx$ is a galaxy with no triangle.
Theorem (12) the(14)$\underline{Remark}$$\underline{red}r\infty ak\underline{of}$a -oarsimonious$2-\underline{multi}-\alpha ra_{-}oh$Byis a salaxv.

. The Erd\"os/Gallai Theorem gives necessary and sufficient conditions that theparsimonious

2-multigraphs in a class$\mathfrak{G}_{2}(D)$have empty red graphs (i.e. all blue edges).

These conditions areis even$(i=1, \ldots,n)$ ,(15)

$d$

(16)

$d_{1}+\cdots+d_{n}\equiv 0(mod 4)$ ,(17)$\sum^{k}d_{i}\leq 2k(k-1)+\sum^{n}$

$i$

$i=1$

$\min\{2k,d_{i}\}$$i=k+1$$\zeta$$(k=1, \ldots,n)$.

ご$L-\mathfrak{n}\wedge$

ゼ(Theclearly have to be even.

$d_{i}$

sequence$(d_{1}/2, \ldots,d_{n}/2)$

Now apply the Erd\"os/Gallai Theorem to the degreeand color all edges of the re ulting graph blue.) Condition (17) is

the Chungphaisan condition (4). If we retain the condition (15), the only other possibility foris$d_{1}+\cdots+d_{n}$(18)$d_{1}+\cdots+d_{n}\equiv 2$

Since the(mod 4).

are even, the red graph of a parsimonious 2-multigraph cannot contain any$d_{i}$

stars. It follows that (15), (17), and (18) are necessary and sufficient conditions in order thatthe parsimonious 2-multigraphs in$\mathfrak{G}_{2}(D)$have red graphs consisting only of a red triangle.

For the two cases discussed in Remark (14) there are algorithms to construct aparsimonious 2-multigraph in a nonempty class$\mathfrak{G}_{2}(D)$. In the. case that (15), (16), and (17)are satisfied it suffices to apply the well-known algorithm of Havel and Hakimi to the degree
sequence$(d_{1}/2, \ldots, d_{n}/2)$

and then to color all edges of the resulting graph blue. In the casethat (15), (17), and (18) are satisfied the algorithm of Havel and Hakimi can be refined to
produce a parsimonious

2-multigraph (the problem is to decide where the red edges of thetriangle go).

(19)

class

$\underline{Problem}$$\mathfrak{G}_{2}(D)$.

Find an algorithm to construct a parsimonious 2-multigraph in a nonempty.

We now consider the question:
parsimonious 2-multigraphs inA collection
for each$H\in Q$$g$$\underline{one}$

What kinds of red graphs [galaxies] can occur in theclass$\mathfrak{G}_{2}(D)$?

of galaxies is $class- com_{-}Datible$ provided there is a classthere is a parsimonious

isomorphic to H.

ム

2-multigraph$G_{H}\in \mathfrak{G}_{2}(D)$$\mathfrak{G}_{2}(D)$such thatwhose red graph is$\cdot$

122

(20)

ma. The galaxies of a class-compatible collection 9 of galaxies contain(21) The same number(22) The same number$\rho$$\mu$of edges (by parsimony),of vertices of odd degree (the number of odd components of thedegree sequence D).

If we denote by$\Delta$( $=0$ or 1) the number of triangles in a galaxy, then the number of oddstars [stars whose center has odd degree] equals
galaxies$i_{J}\iota$$\mu-\rho+3\Delta$. But we do not know whether thea class-compatible collection all have the same value of$\Delta$(thus we do not knowwhether they have the same number of odd stars). We do however have the following result.

(23)$\ovalbox{\tt\small REJECT} ore$$\underline{and}\underline{the}$stars).

(24)

Let

$g\underline{be}\underline{a}\underline{collection}$same number$\underline{of}$$\mu$verticesof stellar galaxies$\underline{of}\underline{odd}$$havin\underline{\not\subset}$

the same number$\rho$

Ofdegree (eouivalentlv the same number$\underline{e}4*es$$\underline{of}$odd.

$\underline{Then}9\underline{is}\underline{class- com_{-}natible}$$\ovalbox{\tt\small REJECT} 1e$. The three galaxies below (with(25) Qu stio .

$\rho=7$

and$\mu=8$) are class-compatible:

Are the following two galaxies (one of which has a triangle and the other ofwhich does not) class compatible?

’7

輪二The preceding theory has an analogue for bipartite 2-multigraphs with prescribed degree

sequence. The vertices of a bipartite 2-multigraph are partitioned into two sets X andwith each edge joining vertices from different sets.
$S=(s_{1}, \ldots,s_{n})$We let$R=$

the class of bipartite 2-multigraphs with these degree sequences$\_{2}(R,S)$

corresponds to the classand column sum vector(26)$\underline{Exam_{-}o1e}$$S$$\mathfrak{U}_{2}(R,S)$

$R$

and

$(r_{1}, \ldots, r_{m})$be the degree sequences of the vertices in the two parts. Let$\_{2}(R,S)$

andS.

$Y$

denote

The classof all (0,1,2)-matrices with row sum vector$R$(use the reduced adjacency matrix).

.

$y_{1}\backslash$$y_{2}$$y_{3}$$\{\begin{array}{lll}2 0 20 l 0l 2 2\end{array}\}$$x_{2}^{1}x_{3}x$$R=(4,1,5)$ ,$S=(3,3,4)$

The notion of parsimony carries over to the classobtain that a matrix A in
$O’ s$$\mathfrak{U}_{2}(R,S)$$\mathfrak{B}_{2}(R,S)$.

In terms of$\mathfrak{U}_{2}(R,S)$

is parsimonious provided it has the largest number of(equivalently the smallest number of l’s, equivalently the largest number of

all matrices in$\mathfrak{U}_{2}(R,S)$$2’ s$) among.

Arguments analogous to those forparsimonious bipartite

we$\mathfrak{G}_{2}(D)$allow one to conclude that the red graphs of

2-multigraphs have their connected components equal to stars.

Because of the bipartite assumption there can be no triangle, however a different difficultyarises.

Some stars$K_{1,t}(t>1)$

have their center inとX

(corresponding in the matrix.

$tt$ ’轟:..

.

$L^{g,}A^{Y}$

formulation to l’s in the same row) while other stars$K_{t,1}$$(t>1)$ have their center in(corresponding to l’s in the same column). The former are called

are called$cA!4mn\underline{stars}$.

$K_{1,2}$$\underline{E_{Xam_{-}D}1e}$while the latter

Then there are the ambi uous (or unoriented) stars(corresponding to a 1 which is the only 1 in its row(27)$\underline{row}\underline{stars}$$\underline{and}$

$Y$

$K$

1,1

the only 1 in its column.

.

(rowstar)$\{\begin{array}{llll}1 1 1 1 l 1\end{array}\}$$rightarrow K_{1,1}$ (ambiguous star)

We use the concepts of a galaxy and of class-compatibility of galaxies in an analogous

way to that used above. If a collection of galaxies is class-compatible then they have(28) the same number(29) the same number(30) the same number
In addition since$\rho$$\lambda$$\nu$

of l’s (edges),of rows with an odd number of l’s,of columns with an odd number of 1’s.

$\lambda+\nu-\rho$equals the number of odd stars (includes ambiguous stars), theyhave(31) the same number$\lambda$

of odd stars.

9,$\sim^{-\wedge\prime;\not\subset_{\}}}i\wedge:\vee r,$(32)$\underline{Theorem}$$\infty rovide$$arrow alaxr$

suit. A collection of$\underline{is}-\underline{oossible}\underline{to}$$\underline{that}$assigneach galaxv$\underline{\alpha}-laxies\underline{with}\underline{the}\underline{same}$$g\underline{n}$orientation (row$\underline{has}\underline{the}$same number gf$\lambda$$\rho,$$\underline{or}\underline{column}$$\underline{odd}$row),$\underline{and}$$\underline{to}$is class-com atible$\nu$each ambi uous star of$\underline{stars}\underline{and}\underline{the}$samg number$\underline{ea}sh$$\underline{of}\underline{odd}$

column stars.

The preceding theorem may be true without the orientation assumption.

(33)$\frac{E_{XamD}1e}{-}$

The following three galaxies have$\rho=5$,$\lambda=3$

and$\nu=3$but do not atisfy$s$the orientation assumption in Theorem (3.2).

1 oddcolumn star

1 odd star(row or column?)

1 odd
row star

Are these galaxies class-compatible?

REFERENCES
1.

Richard A. Brualdi and T. S. Michael, The class of 2-multigraphs with a prescribed
degree sequence, Linear and Multilinear Algebra, to appear.

2.

, l’s, and $2’ s$ with
Richard A. Brualdi and T. S. Michael, The class of matrices of] $ications$ , to appear.
prescribed row and column sums, Linear Algebra and$O’ s$$i\underline{ts}A_{-}D_{-}D$1$\sigma$