Article in press
Authors:
Title:
On link-irregular graphs
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2023-01-19 , Revised: 2023-09-06 , Accepted: 2023-09-08 , Available online: 2023-10-12 , https://doi.org/10.7151/dmgt.2521
Abstract:
The subgraph of a graph $G$ that is induced by the set of neighbors of a
vertex $v$ of $G$ is the link of $v$. If every two distinct vertices of $G$
have non-isomorphic links, then $G$ is link-irregular. It is shown that there
exists a link-irregular graph of order $n$ if and only if $n \ge 6$. The degree
set ${\cal D}(G)$ of $G$ is the set of degrees of the vertices of $G$. While there
is no link-irregular graph $G$ of order $n$ such that $|{\cal D}(G)| \in \{n, n-1\}$,
it is shown that there exists a link-irregular graph $G$ of order $n$ such that
$|{\cal D}(G)|=n-2$ if and only if $n \ge 7$. Further, for each pair $(d, n)$ of
integers with $3 \le d \le 8$ and $n \ge d+4$, there is a link-irregular graph
of order $n$ whose degree set consists of $n-d$ elements. The link-irregular
ratio lir$(G)$ of a link-irregular graph $G$ is defined as $|{\cal D}(G)|/|V(G)|$.
For the set ${\cal L}$ of link-irregular graphs, it is shown that $\sup\{ \textrm{lir}(G):
G \in {\cal L}\} = 1$ and that $0 \le \inf\{ \textrm{lir}(G): G \in {\cal L}\}\le 1/9$. Other
results, problems, and conjectures on link-irregular graphs are also presented.
Keywords:
degree of a vertex, link of a vertex, link-irregular graph
References:
- A. Ali, G. Chartrand and P. Zhang, Irregularity in Graphs (Springer, New York, 2021).
https://doi.org/10.1007/978-3-030-67993-4 - M. Behzad and G. Chartrand, No graph is perfect, Amer. Math. Monthly 74 (1967) 962–963.
https://doi.org/10.2307/2315277 - A. Blass, F. Harary and Z. Miller, Which trees are link graphs$?$, J. Combin. Theory Ser. B 29 (1980) 277–292.
https://doi.org/10.1016/0095-8956(80)90085-4 - M. Brown and R. Connelly, On graphs with constant link, in: New Directions in the Theory of Graphs, F. Harary (Ed(s)), (Academic Press, New York 1973) 19–51.
- G. Exoo and R. Jajcay, Dynamic cage survey, Electron. J. Combin. (2013) #DS16.
https://doi.org/10.37236/37 - J.I. Hall, Locally Petersen graphs, J. Graph Theory 4 (1980) 173–187.
https://doi.org/10.1002/jgt.3190040206 - P. Hell, Graphs with given neighbourhoods I, in: Problèmes Combinatoires et Théorie des Graphes, Proc. Colloq. Orsay, (Paris 1978) 219–223.
- P.G. Tait, Remarks on the colouring of maps, in: Proc. Royal Soc. Edinburgh 10 (1880) 729.
- A.A. Zykov, Problem $30$, in: Theory of Graphs and its Applications, Proc. Symp. Smolenice, (Prague 1964) 164–165.
Close