×

Friendship two-graphs. (English) Zbl 1228.05148

Summary: A friendship graph is a graph in which every two distinct vertices have exactly one common neighbor. All finite friendship graphs are known, each of them consists of triangles having a common vertex. We extend friendship graphs to two-graphs, a two-graph being an ordered pair \(G = (G_{0}, G_{1})\) of edge-disjoint graphs \(G_{0}\) and \(G_{1}\) on the same vertex-set \(V(G_{0}) = V(G_{1})\). One may think that the edges of \(G\) are colored with colors 0 and 1. In a friendship two-graph, every unordered pair of distinct vertices \(u, v\) is connected by a unique bicolored 2-path. The pairs of adjacency matrices of friendship two-graphs are solutions to the matrix equation \(AB + BA = J - I\), where \(A\) and \(B\) are \(n \times n\) symmetric \(0 - 1\) matrices, \(J\) is an \(n \times n\) matrix with every entry being 1, and \(I\) is the identity \(n \times n\) matrix. We show that there is no finite friendship two-graph with minimum vertex degree at most two. However, we construct an infinite such graph, and this construction can be extended to an infinite (uncountable) family. Also, we find a finite friendship two-graph, conjecture that it is unique, and prove this conjecture for the two-graphs that have a dominating vertex.

MSC:

05C15 Coloring of graphs and hypergraphs
05C07 Vertex degrees
Full Text: DOI

References:

[1] Bondy, J.A.: Kotzig’s conjecture on generalized friendship graphs–a survey. In: Cycles in Graphs (Burnaby, B.C., 1982). North-Holland Math. Stud., vol. 115, pp. 351–366. North-Holland, Amsterdam (1985)
[2] Boros E., Gurvich V.: Vertex- and edge-minimal and locally minimal graphs. Discrete Math. 309(12), 3853–3865 (2009) · Zbl 1229.05131 · doi:10.1016/j.disc.2008.10.020
[3] Chvátal V., Graham R.L., Perold A.F., Whitesides S.H.: Combinatorial designs related to the strong perfect graph conjecture. Discrete Math. 26(2), 83–92 (1979) · Zbl 0403.05017 · doi:10.1016/0012-365X(79)90114-6
[4] Erdos P., Rényi A., Sós V.T.: On a problem of graph theory. Studia Sci. Math. Hungar. 1, 215–235 (1966)
[5] Gurvich V.: Some properties and applications of complete edge-chromatic graphs and hypergraphs. Soviet Math. Dokl. 30(3), 803–807 (1984) · Zbl 0604.05018
[6] Gurvich V.: Decomposing complete edge-chromatic graphs and hypergraphs. Revisited, Discrete Appl. Math. 157, 3069–3085 (2009) · Zbl 1209.05081 · doi:10.1016/j.dam.2009.06.026
[7] Kostochka A.V.: The nonexistence of certain generalized friendship graphs. In: Combinatorics (Eger, 1987). Colloq. Math. Soc. János Bolyai, vol. 52. North-Holland, Amsterdam (1988) · Zbl 0679.05048
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.