×

zbMATH — the first resource for mathematics

A worthy family of semisymmetric graphs. (English) Zbl 1021.05048
Summary: We construct semisymmetric graphs in which no two vertices have exactly the same neighbors. We show how to do this by first considering bi-transitive graphs, and then we show how to choose two such graphs so that their product is regular. We display a family of bi-transitive graphs \(D_{N}(a,b)\) which can be used for this purpose and we show that their products are semisymmetric by applying vectors due to A. V. Ivanov [Ann. Discrete Math. 34, 273-286 (1987; Zbl 0629.05040)].

MSC:
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bouwer, I.Z., An edge but not vertex transitive cubic graph, Bull. can. math. soc., 11, 533-535, (1968) · Zbl 0182.58102
[2] Bouwer, I.Z., On edge but not vertex transitive regular graphs, J. combin. theory ser. B, 12, 32-40, (1972) · Zbl 0228.05114
[3] S.-F. Du, Construction of Semisymmetric graphs, Graph Theory Notes of New York, XXIX, 1995.
[4] Du, S.-F.; Marus̆ic̆, D., An infinite family of biprimitive semisymmetric graphs, J. graph theory, 32, 3, 217-228, (1999) · Zbl 0943.05043
[5] Du, S.-F.; Marus̆ic̆, D., Biprimitive semisymmetric graphs of smallest order, J. algebraic combin., 9, 2, 151-156, (1999) · Zbl 0937.05049
[6] Du, S.F.; Xu, M.Y., A classification of semisymmetric graphs of order 2pq, Comm. algebra, 28, 6, 2685-2715, (2000) · Zbl 0944.05051
[7] Folkman, J., Regular line-symmetric graphs, J. combin. theory, 3, 215-232, (1967) · Zbl 0158.42501
[8] F. Harary, E. Dauber, Line-symmetric but not point-symmetric graphs, unpublished.
[9] Imrich, W.; Izbicki, H., Associative products of graphs, Monatsh. math., 80, 4, 277-281, (1975) · Zbl 0328.05136
[10] M.E. Iofinova, A.A. Ivanov, Biprimitive cubic graphs, in: M.Kh. Klin, I.A. Faradzhev (Eds.), Investigations in the Algebraic Theory of Combinatorial Objects, Institute for System Studies, Moscow, 1985, pp. 124-134. · Zbl 0706.05025
[11] Ivanov, A.V., On edge but not vertex transitive regular graphs, Ann. discrete math., 34, 273-286, (1987) · Zbl 0629.05040
[12] Jensen, T.R.; Toft, B., Graph coloring problems, (1995), Wiley New York · Zbl 0971.05046
[13] M.H. Klin, On edge but not vertex transitive graphs, Coll. Math. Soc. J. Bolyai (Algebraic Methods in Graph Theory, Vol. 25, Szeged, 1978), Budapest, 1981, pp. 399-403.
[14] Marus̆ic̆, D., Constructing edge-but not vertex-transitive graphs, J. graph theory, 35, 152-160, (2001) · Zbl 1021.05050
[15] Marus̆ic̆, D.; Pisanski, T., The gray graph revisited, J. graph theory, 35, 1-7, (2000) · Zbl 1021.05049
[16] Marus̆ic̆, D.; Potocnik, P., Semisymmetry of generalized folkman graphs, European J. combin., 22, 333-349, (2001) · Zbl 0979.05056
[17] Miller, D.J., The categorical product of graphs, Canad. J. math., 20, 1511-1521, (1968) · Zbl 0167.21902
[18] L. Powell, The vertex next door, NAU REU Reports, 2000.
[19] Weichsel, P.M., The Kronecker product of graphs, Proc. amer. math. soc., 13, 47-52, (1962) · Zbl 0102.38801
[20] S.E. Wilson, Semi-transitive graphs, J. Graph Theory, to be published.
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.