# zbMATH — the first resource for mathematics

Graphic matrices. (English) Zbl 0662.05045
In the paper finite simple graphs are considered. To every graph G a matrix $$M_ G$$ of non-negative integers which informs us about the degrees of the neighbours of each vertex can be assigned. Let $$G=(V,E)$$ be a finite simple graph, where $$V=\{v_ 1,...,v_ n\}$$ is the vertex set, and let $$D(G)=\{d_ 1,...,d_ k\}\quad (d_ 1>d_ 2>...>d_ k)$$ be the sequence of degrees of vertices of V, $$\Gamma (v)=\{u\in V| \quad (u,v)\in E\},\quad V_ i=\{v\in V| \quad \deg v=d_ i\},\quad E_{ij}=\{(u,v)| \quad u\in V_ i,\quad v\in V_ j\},\quad t^ i(v)=| V_ i\cap \Gamma (v)|.$$ A (k$$\times n)$$-matrix $$M_ G=(m_{ij})$$ with $$m_{ij}=t^ i(v_ j)$$ for all $$i\in \{1,...,k\}$$, $$j\in \{1,...,n\}$$ is called the distribution matrix of G. A matrix M is graphic if $$M=M_ G$$ for some graph G. In the paper graphic matrices and the set of all graphs with the same vertex set and with the same distribution matrix is characterized.
Reviewer: V.Fleischer

##### MSC:
 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
##### Keywords:
(*)-switching operation; finite simple graphs; matrix
Full Text:
##### References:
  BALABAN A. T., KEREK F.: Graphs of parallel and or substitution reactions. Rev. Roum de Chemie 19, 1974, No. 4, 631-647.  BERGE C.: Graphs and Hypergraphs. North-Holland, Amsterdam 1973. · Zbl 0483.05029  EGGLETON R. B.: Graphic sequences and graphic polynomials: a report. Infinite and Finite Sets. Colloqu. Math. Soc. J. Bolyai 10, 1973, 385-392.  EGGLETON R. B., HOLTON D. A.: Graphic sequences. Combinatorial Math. VI. Proc. 6th Australian Conf. on Combinatorial Math., Armidale, 1978, Springer-Verlag 1979, 1-10. · Zbl 0425.05051  EGGLETON R. B., HOLTON D. A.: Simple and multigraphic realizations of degree sequences. Combinatorial Math. VIII. Proc. Geelong, Australia 1980, Springer-Verlag 1981, 155-172. · Zbl 0486.05059  ERDÖS P., GALLAI T.: Graphs with prescribed degrees of vertices (in Hungarian). Mat. Lapok 11, 1960, 264-274.  EVANS C. W.: Some properties of semi-regular graphs. match 6, 1979, 117-135. · Zbl 0442.05059  GALE D.: A theorem in folows in networks. Pacific J. Math. 7, 1957, 1073-1082. · Zbl 0087.16303  HAKIMI S. L.: On the realizability of a set of integers as degrees of the vertices of a linear graph. I. J. SIAM 10, 1962, 496-506. · Zbl 0109.16501  HARARY F.: Graph Theory. Addison-Vesley, Mass. 1969. · Zbl 0196.27202  HAVEL V.: A remark on the existence of finite graphs (in Czech). Čas. pěst. mat. 80, 1955, 477-480. · Zbl 0068.37202  MAJCHER Z.: Matrices representable by graphs.: Teubner-Texte zur Mathematik. Band 59, Proc. of the Third Czechoslovak Symposium on Graph Theory, Prague 1982, BSB B. G. Teubner Verlagsgesellschaft, 1983, 178-182.  MAJCHER Z.: On some regularities of graphs II. Čas. p\?st. mat. 109, 1984, 380-388. · Zbl 0576.05058  MAJCHER Z.: Algorithms for constructing paths in a graph of realizations of a degree sequence. · Zbl 0627.05042  PŁONKA J.: On R-regular graphs. Colloquium Math. 46, 1982, 131-134. · Zbl 0496.05047  PŁONKA J.: On some regularities of graphs I. Čas. p\?st. mat. 107, 1982, 231-240. · Zbl 0505.05058  RAMA CHANDRAN S.: Nearly regular graphs and their reconstruction. Graph Theory Newsletter B, 3, 1978.  TAYLOR R.: Constrained switchings in graphs. Combinatorial Math. VIII. Proc. Geelong, Australia 1980, Springer-Verlag 1981, 314-336.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.