Geodesic
Claw-free strictly Deza graphs
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 367-387.

Voir la notice de l'article provenant de la source Math-Net.Ru

A Deza graph with parameters $(v,k,b,a)$ is a $k$-regular graph, which has exactly $v$ vertices and any two distinct vertices have either $a$ or $b$ common neighbors. A strictly Deza graph is a Deza graph of diameter $2$ that is not strongly regular. A claw-free graph is a graph in which no induced subgraph is a complete bipartite graph $K_{1,3}$. We proved if graph $G$ is a claw-free strictly Deza graph which contains a $3$-coclique then $G$ is either an $4 \times n$-lattice, where $n > 2$, $n \neq 4$, or the $2$-extension of the $3 \times 3$-lattice, or two strictly Deza graphs with the parameters $(9,4,2,1)$, or two strictly Deza graphs with the parameters $(12,6,3,2)$, or a Deza line graph with the parameters $(20,6,2,1)$.
Keywords: strictly Deza graphs, claw-free graphs. 
@article{SEMR_2017_14_a72,
     author = {V. V. Kabanov and A. V. Mityanina},
     title = {Claw-free strictly {Deza} graphs},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {367--387},
     publisher = {mathdoc},
     volume = {14},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2017_14_a72/}
}
TY  - JOUR
AU  - V. V. Kabanov
AU  - A. V. Mityanina
TI  - Claw-free strictly Deza graphs
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2017
SP  - 367
EP  - 387
VL  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2017_14_a72/
LA  - en
ID  - SEMR_2017_14_a72
ER  - 
%0 Journal Article
%A V. V. Kabanov
%A A. V. Mityanina
%T Claw-free strictly Deza graphs
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2017
%P 367-387
%V 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2017_14_a72/
%G en
%F SEMR_2017_14_a72
V. V. Kabanov; A. V. Mityanina. Claw-free strictly Deza graphs. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 14 (2017), pp. 367-387. http://geodesic.mathdoc.fr/item/SEMR_2017_14_a72/

[1] L. W. Beineke, “Characterizations of derived graphs”, Journal of Combinatorial Theory, 9:2 (1970), 129–135 | DOI | MR | Zbl

[2] D. P. Sumner, “Graphs with $1$-factors”, Proceedings of the American Mathematical Society, 42:1 (1974), 8–12 | MR | Zbl

[3] M. Las Vergnas, “A note on matchings in graphs”, Cahiers du Centre d'Études de Recherche Opérationnelle, 17:2–3–4 (1975), 257–260 | MR | Zbl

[4] N. Sbihi, “Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoile”, Discrete Mathematics, 29:1 (1980), 53–76 | DOI | MR | Zbl

[5] G. J. Minty, “On maximal independent sets of vertices in claw-free graphs”, Journal of Combinatorial Theory, Series B, 28:3 (1980), 284–304 | DOI | MR | Zbl

[6] F. Maffray, B. A. Reed, “A description of claw-free perfect graphs”, Journal Combinatorial Theory, Series B, 75:1 (1999), 134–156 | DOI | MR | Zbl

[7] M. Erickson, S. Fernando, W. H. Haemers, D. Hardy, J. Hemmeter, “Deza graphs: a generalization of strongly regular graphs”, Journal of Combinatorial Designs, 7:6 (1999), 395–405 | 3.0.CO;2-U class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[8] R. Faudree, E. Flandrin, Z. Ryjáček, “Claw-flee graphs—a survey”, Discrete Mathematics, 164:1–3 (1997), 87–147 | DOI | MR | Zbl

[9] M. Chudnovsky, P. Seymour, “Claw-free graphs. V. Global structure”, Journal of Combinatorial Theory, Series B, 98:6 (2008), 1373–1410 | DOI | MR | Zbl

[10] A. E. Brouwer, M. Numata, “A characterization of some graphs which do not contain $3$-claws”, Discrete Mathematics, 124:1–3 (1994), 49–54 | DOI | MR | Zbl

[11] A. V. Mityanina, “On $K_{1,3}$-free strictly Deza graphs”, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 22, no. 1, 2016, 231–234 (Russian) | DOI | MR

[12] SibirskiĭMatematicheskiĭZhurnal, 39:55 (1998), 1054–1059 | DOI | MR | Zbl

[13] Trudy Instituta Matematiki i Mekhaniki UrO RAN, 18, no. 1, 2012, 165–177 | DOI | MR | Zbl

[14] Matematicheskie Zametki, 60:4 (1996), 495–503 | DOI | DOI | MR | Zbl

[15] S. V. Goryainov, L. V. Shalaginov, “On Deza graphs on $14$, $15$ and $16$ vertices”, Siberian Electronic Mathematical Reports, 8 (2011), 105–115 (Russian, English summary) | MR | Zbl

[16] Matematicheskie Zametki, 63:3 (1998), 407–413 | DOI | DOI | MR | Zbl

[17] A. C. M. Van Rooij, H. S. Wilf, “The interchange graph of a finite graph”, Acta Mathematica Academiae Scientiarum Hungaricae, 16:3 (1965), 263–269 | MR | Zbl