Graphs, friends and acquaintances

View/ Open
Issue date
2018Suggested citation
Dalfó, Cristina;
Fiol, Miguel Angel;
.
(2018)
.
Graphs, friends and acquaintances.
The Electronic Journal of Graph Theory and Applications, 2018, vol. 6, núm. 2, p. 282-305.
https://doi.org/10.5614/ejgta.2018.6.2.8.
Metadata
Show full item recordAbstract
A graph is a mathematical object modeling the existence of a certain relation between pairs of elements of a given set. Many of the first results concerning graphs made reference to relationships between groups of people. In this article, we comment on four results of this kind: the Handshake lemma (related to graph colorings and Boolean algebra), a lemma on known and unknown people at a cocktail party (to Ramsey theory), a theorem on friends in common (to distance-regularity and coding theory), and Hall's Marriage theorem (to the theory of networks). These four areas of graph theory, often with problems which are easy to state but difficult to solve, are extensively developed and currently give rise to much research work. As examples of representative problems and results of these areas we may cite the following: the Four Colors Theorem (4CTC), the Ramsey numbers, problems of the existence of distance-regular graphs and completely regular codes, and finally the study of topological proprieties of interconnection networks.
Is part of
The Electronic Journal of Graph Theory and Applications, 2018, vol. 6, núm. 2, p. 282-305European research projects
Collections
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as cc-by-sa (c) Cristina Dalfo et al., 2018
Related items
Showing items related by title, author, creator and subject.
-
The spectral excess theorem for graphs with few eigenvalues whose distance- 2 or distance-1-or-2 graph is strongly regular
Dalfó, Cristina; Fiol, Miguel Angel; Koolen, Jack (Taylor & Francis, 2018-07-13)We study regular graphs whose distance-2 graph or distance-1-or-2 graph is strongly regular. We provide a characterization of such graphs Γ (among regular graphs with few distinct eigenvalues) in terms of the spectrum and ... -
On Middle Cube Graphs
Dalfó, Cristina; Fiol, Miguel Angel; Mitjana, Margarida (Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia, 2015)We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The ... -
A general method to obtain the spectrum and local spectra of a graph from its regular partitions
Dalfó, Cristina; Fiol, Miguel Angel (International Linear Algebra Society, 2020-07-12)It is well known that, in general, part of the spectrum of a graph can be obtained from the adjacency matrix of its quotient graph given by a regular partition. In this paper, a method that gives all the spectrum, and also ...