Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

A role for doubly stochastic matrices in graph theory


Authors: D. J. Hartfiel and J. W. Spellmann
Journal: Proc. Amer. Math. Soc. 36 (1972), 389-394
MSC: Primary 05C20
DOI: https://doi.org/10.1090/S0002-9939-1972-0316296-3
MathSciNet review: 0316296
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper represents a strongly connected digraph as a doubly stochastic matrix. It then uses this doubly stochastic representation to prove several theorems concerning the critical arcs of strongly connected graphs.


References [Enhancements On Off] (What's this?)

  • [1] Claude Berge, Théorie des graphes et ses applications, Dunod, Paris, 1958; English transl., Wiley, New York, 1962. MR 21 #1608; MR 24 #A2381. MR 0102822 (21:1608)
  • [2] R. A. Brualdi, Convex sets of non-negative matrices, Canad. J. Math. 20 (1968), 144-157. MR 36 #2636. MR 0219556 (36:2636)
  • [3] F. R. Gantmaher, The theory of matrices, GITTL, Moscow, 1953; English transl., Chelsea, New York, 1959. MR 16, 438; MR 21 #6372c. MR 0065520 (16:438l)
  • [4] Dennis P. Geller, Minimally strong digraphs, Proc. Edinburgh Math. Soc. (2) 17 (1970), 15-22. MR 42 #1718. MR 0266815 (42:1718)
  • [5] Frank Harary, Graph theory, Addison-Wesley, Reading, Mass., 1969. MR 41 #1566. MR 0256911 (41:1566)
  • [6] D. J. Hartfiel, Concerning diagonal similarity of irreducible matrices, Proc. Amer. Math. Soc. 30 (1971), 419-425. MR 0281731 (43:7446)
  • [7] W. B. Jurkat and H. J. Ryser, Term rank and permanents of nonnegative matrices, J. Algebra 5 (1967), 342-357. MR 35 #6575. MR 0215740 (35:6575)
  • [8] H. E. Robbins, A theorem on graphs, with an application to a problem of traffic control, Amer. Math. Monthly 46 (1939), 281-283. MR 1524589
  • [9] Richard Sinkhorn and Paul Knopp, Problems involving diagonal products in nonnegative matrices, Trans. Amer. Math. Soc. 136 (1969), 67-75. MR 38 #2151. MR 0233830 (38:2151)
  • [10] Richard S. Varga, Matrix iterative analysis, Prentice-Hall, Englewood Cliffs, N.J., 1962. MR 28 #1725. MR 0158502 (28:1725)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05C20

Retrieve articles in all journals with MSC: 05C20


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1972-0316296-3
Keywords: Digraph, doubly stochastic matrices, critical arcs
Article copyright: © Copyright 1972 American Mathematical Society

American Mathematical Society