×

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.)
PDFBibTeX XMLCite
Full Text: EuDML

References:

[1] BALABAN A. T., KEREK F.: Graphs of parallel and or substitution reactions. Rev. Roum de Chemie 19, 1974, No. 4, 631-647.
[2] BERGE C.: Graphs and Hypergraphs. North-Holland, Amsterdam 1973. · Zbl 0483.05029
[3] EGGLETON R. B.: Graphic sequences and graphic polynomials: a report. Infinite and Finite Sets. Colloqu. Math. Soc. J. Bolyai 10, 1973, 385-392.
[4] 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
[5] 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
[6] ERDÖS P., GALLAI T.: Graphs with prescribed degrees of vertices (in Hungarian). Mat. Lapok 11, 1960, 264-274.
[7] EVANS C. W.: Some properties of semi-regular graphs. match 6, 1979, 117-135. · Zbl 0442.05059
[8] GALE D.: A theorem in folows in networks. Pacific J. Math. 7, 1957, 1073-1082. · Zbl 0087.16303
[9] 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
[10] HARARY F.: Graph Theory. Addison-Vesley, Mass. 1969. · Zbl 0196.27202
[11] HAVEL V.: A remark on the existence of finite graphs (in Czech). Čas. pěst. mat. 80, 1955, 477-480. · Zbl 0068.37202
[12] 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.
[13] MAJCHER Z.: On some regularities of graphs II. Čas. p\?st. mat. 109, 1984, 380-388. · Zbl 0576.05058
[14] MAJCHER Z.: Algorithms for constructing paths in a graph of realizations of a degree sequence. · Zbl 0627.05042
[15] PŁONKA J.: On R-regular graphs. Colloquium Math. 46, 1982, 131-134. · Zbl 0496.05047
[16] PŁONKA J.: On some regularities of graphs I. Čas. p\?st. mat. 107, 1982, 231-240. · Zbl 0505.05058
[17] RAMA CHANDRAN S.: Nearly regular graphs and their reconstruction. Graph Theory Newsletter B, 3, 1978.
[18] 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.