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.
- 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. 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
Index Terms
- Analysis of Graphs by Connectivity Considerations
Recommendations
On Group Connectivity of Graphs
Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero Z 3-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