Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/1341
Title: Primitive Diameter 2-Critical Graphs
Authors: Radosavljević, Jovan
Stanić, Zoran 
Živković, Miodrag
Keywords: cone;critical graph;diameter;Erdős–Rényi theorem;Hamiltonian graph;primitive graph;self-centered graph
Issue Date: 1-Jan-2024
Publisher: Beograd : Matematički institut SANU
Journal: Publications de l'Institut Mathematique
Abstract: 
We study diameter 2-critical graphs (for short, D2C graphs), i.e. graphs of diameter 2 whose diameter increases after removing any edge. Our results include structural considerations, new examples and a particular relationship with minimal 2-self-centered graphs stating that these graph classes are almost identical. We pay an attention to primitive D2C graphs (PD2C graphs) which, by definition, have no two vertices with the same set of neighbours. It is known that a graph of diameter 2 and order n, which has no dominating vertex, has at least 2n − 5 edges, and the graphs that attain this bound are also known. It occurs that exactly three of them are PD2C. The next natural step is to consider PD2C graphs with 2n − 4 edges. In this context, we determine an infinite family of PD2C graphs which, for every n?> 6, contains exactly one graph with 2n − 4 edges. We also prove that there are exactly seven Hamiltonian PD2C graphs with the required number of edges. We show that for n 6 13, there exists a unique PD2C graph with 2n − 4 edges that does not belong to the obtained family nor is Hamiltonian. It is conjectured that this is a unique example of such a graph.
URI: https://research.matf.bg.ac.rs/handle/123456789/1341
ISSN: 03501302
DOI: 10.2298/PIM2429021R
Rights: Attribution 3.0 United States
Appears in Collections:Research outputs

Files in This Item:
File Description SizeFormat
publn135p21-32.pdf298.08 kBAdobe PDF
View/Open
Show full item record

Page view(s)

25
checked on Dec 23, 2024

Download(s)

2
checked on Dec 23, 2024

Google ScholarTM

Check

Altmetric

Altmetric


This item is licensed under a Creative Commons License Creative Commons