article

Free access

Analysis of Graphs by Connectivity Considerations

Author:

C. V. RamamoorthyAuthors Info & Claims

Journal of the ACM (JACM), Volume 13, Issue 2

Pages 211 - 222

https://doi.org/10.1145/321328.321332

Published: 01 April 1966 Publication History

PDF eReader

Abstract

Discrete sequential systems, such as sampled data systems, discrete Markov processes, linear shift register generators, computer programs, sequential code generators, and prefixed comma-free codes, can be represented and studied in a uniform manner by directed graphs and their generating functions. In this paper the properties of the generating functions are examined from certain connectivity considerations of these graphs.

References

[1]

CHEN, Y. C. AND WING, O. Connectivity of directed graphs. Proc. of Allerton Conf. 0 Circuit and System Theory, U. of Illinois, Sept. 1964.

Google Scholar

[2]

HARIY, F. Some historical and intuitive aspects of graph theory. SiAM Rev. 2, 2 (1960), 123-131.

Google Scholar

[3]

-- ET hL. Structural Models. John Wiley & Sons, New York, 1965.

Google Scholar

[4]

MARIMONT, R. B. A new method of checking the consistency of precedence matrices. J . ACM 6 (1959), 164-171.

Crossref

Google Scholar

[5]

----. Applications of graphs and Boolean matrices to computer programming. SIAM tgev. 2, 4 (1960), 259-268.

Google Scholar

[6]

PROSSER R. Applications of Boolean matrices to tim analysis of flow diagrams. Proc, laastern Joint Comput. Conf. 1959. (Now available from Spartan Books, Washington, D .C.)

Google Scholar

[7]

IAMAMOOItTIY, C.V. Doctoral thesis, ttarvard U., May 1964.

Google Scholar

[8]

--. Representation and analysis of discrete systems using generating functions of abstract graphs. IEEE Int. Cony. Rec. 1965, Pt. 6.

Google Scholar

[9]

--. Connectivity considerations of graphs representing discrete sequential systems. Trans. IEEE EC-I4 (Oct. 1965), 724-727.

Google Scholar

[10]

--. A unitied approach for solving quantitative problems in discrete systems by generating functions of abstract graphs. Proc. IFIP Congr. 1965, Vol. 2, MacMillan Co., New York, 1965.

Google Scholar

[11]

--- Transitions in multi-parameter multi-level discrete systems. IEEE Publ. 4C9, Proc. IEEE Syrup. on Signal Transmission and Processing, 1965.

Google Scholar

[12]

--. Discrete Markov analysis of computer programs. Proc. ACM 20th Nat. Conf., 19(5, p p . 386-392.

Google Scholar

[13]

- Signal coding for transmission and resolution by graph theoretic methods. Proc. First Annual IEEE Communications Cony., 1965, pp. 193-199.

Google Scholar

[14]

---- AND TUFTS, D.W. Reinforced comma-free codes. Cruft Lab. Rep. No. 480, Harvard U., ug. 1965; also Paper, IEEE Int. Symposium on Inf. Theory, 1966.

Google Scholar

Cited By

View all

Hoffmann C(2016)Towards Understanding Dynamic Complexity in Financial Systems Structure‐based Explanatory Modelling of RisksSystems Research and Behavioral Science10.1002/sres.241434:6(728-745)Online publication date: 29-Jun-2016
https://doi.org/10.1002/sres.2414
Srimani PSinha BChoudhury A(2015)A New Algorithm to Determine All the Minimum Edge Sets of a System GraphIETE Journal of Research10.1080/03772063.1978.1145174024:12(534-539)Online publication date: 11-Jul-2015
https://doi.org/10.1080/03772063.1978.11451740
Althoff MKrogh B(2014)Reachability Analysis of Nonlinear Differential-Algebraic SystemsIEEE Transactions on Automatic Control10.1109/TAC.2013.228575159:2(371-383)Online publication date: Feb-2014
https://doi.org/10.1109/TAC.2013.2285751
Show More Cited By

Index Terms

Analysis of Graphs by Connectivity Considerations
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

On Group Connectivity of Graphs

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z ₃-flow and Jaeger et al. [Group connectivity of graphs–a nonhomogeneous analogue of nowhere-zero flow properties, J. Combin. Theory Ser. B 56 (1992) 165-182] further conjectured ...
Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we ...
On the connectivity of bipartite distance-balanced graphs

A connected graph @C is said to be distance-balanced whenever for any pair of adjacent vertices u,v of @C the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In [K. Handa, Bipartite graphs with balanced ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 13, Issue 2

April 1966

138 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321328

Editor:
C. C. Gotlieb

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1966

Published in JACM Volume 13, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

66
Total Citations
View Citations
828
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hoffmann C(2016)Towards Understanding Dynamic Complexity in Financial Systems Structure‐based Explanatory Modelling of RisksSystems Research and Behavioral Science10.1002/sres.241434:6(728-745)Online publication date: 29-Jun-2016
https://doi.org/10.1002/sres.2414
Srimani PSinha BChoudhury A(2015)A New Algorithm to Determine All the Minimum Edge Sets of a System GraphIETE Journal of Research10.1080/03772063.1978.1145174024:12(534-539)Online publication date: 11-Jul-2015
https://doi.org/10.1080/03772063.1978.11451740
Althoff MKrogh B(2014)Reachability Analysis of Nonlinear Differential-Algebraic SystemsIEEE Transactions on Automatic Control10.1109/TAC.2013.228575159:2(371-383)Online publication date: Feb-2014
https://doi.org/10.1109/TAC.2013.2285751
Nettleton D(2013)SurveyComputer Science Review10.1016/j.cosrev.2012.12.0017(1-34)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.cosrev.2012.12.001
Chappell SElmendorf CSchmidt L(2013) LAMP : Logic-Circuit Simulators Bell System Technical Journal10.1002/j.1538-7305.1974.tb02800.x53:8(1451-1476)Online publication date: 29-Jul-2013
https://doi.org/10.1002/j.1538-7305.1974.tb02800.x
Ozaydin BTanik M(2011)SYSTEM MODELING AND ANALYSIS USING COMMUNICATION CHANNELSJournal of Integrated Design & Process Science10.5555/2590478.259047915:1(1-33)Online publication date: 1-Jan-2011
https://dl.acm.org/doi/10.5555/2590478.2590479
Demirezen ZBryant BSkjellum ATanik M(2010)DESIGN SPACE ANALYSIS IN MODEL-DRIVEN ENGINEERINGJournal of Integrated Design & Process Science10.5555/2590457.259045814:1(1-15)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.5555/2590457.2590458
Baer J(2009)Matrice de connexion minimale d'une matrice de précédence donnéeRevue française d'informatique et de recherche opérationnelle. Série rouge10.1051/m2an/196903R1006513:16(65-73)Online publication date: 4-May-2009
https://doi.org/10.1051/m2an/196903R100651
TAO KHSIA P(2008)ON THE STRUCTURE OF DIRECTED GRAPHS WITH APPLICATIONS: A Rapprochement with Systems Theory Part IInternational Journal of General Systems10.1080/030810782085474448:3(147-159)Online publication date: 2-Apr-2008
https://doi.org/10.1080/03081078208547444
TAPIERO C(2007)THE THEORY OF GRAPHS IN BEHAVIORAL SCIENCE*Decision Sciences10.1111/j.1540-5915.1972.tb00526.x3:1(57-81)Online publication date: 7-Jun-2007
https://doi.org/10.1111/j.1540-5915.1972.tb00526.x
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

On Group Connectivity of Graphs

Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

On the connectivity of bipartite distance-balanced graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations