×

zbMATH — the first resource for mathematics

On partially directed p-graphs. (English) Zbl 0608.05037
In the following G may be assumed to be a simple digraph [by results of J. Bosák, Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642, 75-85 (1978; Zbl 0371.05016); Math. Slovaca 29, 181-196 (1979; Zbl 0407.05057)]. G is said to be homogeneous of valency d if \(\text{indegree}(v) = \text{outdegree}(v) = d\) for every vertex v of G. G is a P-graph if for every ordered pair u,v of vertices of G there exists exactly one path from u to v such that the length of the path does not exceed the diameter of G. G is a quasitree if for every ordered pair u,v of vertices of G there exists exactly one path from u to v. G is a T- graph if for every ordered pair u,v of vertices of G there exists exactly one trail from u to v such that the length of the trail does not exceed the diameter of G. A graph of type P(d,k) is a homogeneous P-graph theory of valency d and with a finite diameter k. The main results of the author are as follows. (1) Every P-graph is either a quasitree or a homogeneous block \((=connected\) graph without a cutpoint) with a finite diameter. (2) Every P-graph with diameter at most two is a T-graph. At the end the author raises the following question: For which integers d and k does there exist a graph of type \(P(d,k)\)?
MSC:
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
References:
[1] BOSÁK J.: Grahps with unique walks, trails or paths of given lengths. Theory and Applications of graphs (Proc. Conf. Kalamazoo 1976), Springer-Verlag, Berlin 1978, 75-85.
[2] BOSÁK J.: Geodetic graphs. Combinatorics (Proc. Colloq. Keszthely 1976), North Holland, Amsterdam 1978, 151-172.
[3] BOSÁK J.: Partially directed Moore graphs. Math. Slovaca, 29, 1979, 181-196. · Zbl 0407.05057
[4] BOSÁK J., KOTZIG A., ZNÁM Š.: Strongly geodetic graphs. J. Combinat. Theory, 5, 1968, 170-176. · Zbl 0165.26602
[5] BOSÁK J.: On the k-index of graphs. Discrete Math., 1, 1971, 133-146. · Zbl 0219.05079
[6] HARARY F.: Graph Theory. Addison-Wesley, Reading, Mass. 1969. · Zbl 0196.27202
[7] HÍC P.: On partially directed geodetic graphs. Math. Slovaca, 32, 1982, 255-262. · Zbl 0492.05045
[8] HOFFMAN A. J., SINGLETON R. R.: On Moore graphs with diameters 2 and 3. IBM J. Res. Develop. 4, 1960, 497-504. · Zbl 0096.38102
[9] PLESNÍK J.: One method for proving the impossibility of certain Moore graphs. Discrete Math., 8, 1974, 363-376. · Zbl 0287.05114
[10] PLESNÍK J., ZNÁM Š.: Strongly geodetic dirteted graphs. Acta Fac. Rerum Natur. Univ Comenian Math., 9, 1974, 455-465
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.