Glasnik Matematicki, Vol. 44, No.2 (2009), 259-266.


Damir Vukičević

Department of Mathematics, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia

Abstract.   Let mij(G) be the number of edges of graph G, connecting vertices of degrees i and j. Necessary and sufficient conditions are established on a symmetric matrix M of type Δ × Δ such that there is a tree T for which Mij = mij(T) holds for all i, j.

2000 Mathematics Subject Classification.   05C05, 05C07, 05C90.

Key words and phrases.   Realizability, edge-connectivities, tree.

Full text (PDF) (free access)

DOI: 10.3336/gm.44.2.01


  1. P. Erdös and T. Gallai, Graphs with prescribed degrees of vertices, Mat. Lapok 11 (1960), 264-274 (in Hungarian).

  2. I. Gutman and N. Trinajstic, Graph theory and molecular orbitals. Total π-electron energy of alternant hydrocarbons, Chemical Physics Letters 17 (1972), 535-538.

  3. X. Li and I. Gutman, Mathematical Aspects of Randic-Type Molecular Structure Descriptors, MCM, Kragujevac 2006.

  4. R. Merris, Graph Theory, Wiley, New York, 2001.

  5. A. Milicevic and S. Nikolic, On variable Zagreb indices, Croat. Chem. Acta 77 (2004), 97-101.

  6. S. Nikolic, G. Kovacevic, A. Milicevic and N. Trinajstic, The Zagreb indices 30 years after, Croat. Chem. Acta 76 (2003), 113-124.

  7. M. Randic, Characterization of molecular branching, J. Am. Chem. Soc. 97 (1975), 6609-6615.

  8. D. Veljan, Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001 (in Croatian).

  9. D. Veljan and D. Vukicevic, On acyclic molecular graphs with prescribed numbers of edges that connect vertices with given degrees, J. Math. Chem. 40 (2006), 155-178.
    MathSciNet     CrossRef

  10. D. Vukicevic and A. Graovac, On molecular graphs with valencies 1, 2 and 4 with prescribed number of bonds, Croat. Chem. Acta 77 (2004), 313-319.

  11. D. Vukicevic and A. Graovac, Valence connectivity versus Randic, Zagreb and Modified Zagreb index: a linear algorithm to check discriminative properties of indices in acyclic molecular graphs, Croat. Chem. Acta 77 (2004), 501-508.

  12. D. Vukicevic and A. Graovac, Which valence connectivities are realizing monocyclic molecules: generating algorithm and its application to test discriminative properties of Zagreb and Modified Zagreb index, Croat. Chem. Acta 77 (2004), 481-490.

  13. D. Vukicevic, D. Veljan and N. Trinajstic, Thorny graphs. I. Valence connectivities, MATCH-Commun. Math. Comput. Chem. 55 (2006), 73-82.

Glasnik Matematicki Home Page