Edge-minimal graphs of exponent 2

Olga O'Mahony; Rachel Quinlan

doi:10.1016/j.laa.2017.02.004

Edge-minimal graphs of exponent 2

Olga O'Mahony
, Rachel Quinlan

Mathematics

University of Galway

Research output: Contribution to a Journal (Peer & Non Peer) › Article › peer-review

1 Citation (Scopus)

Abstract

A simple undirected graph G has the me₂-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. This article considers graphs that can be embedded as induced subgraphs of me₂-graphs by the introduction of additional mutually non-adjacent vertices and suitably chosen edges. The main results concern such embeddings of trees.

Original language	English
Pages (from-to)	66-83
Number of pages	18
Journal	Linear Algebra and Its Applications
Volume	542
DOIs	https://doi.org/10.1016/j.laa.2017.02.004
Publication status	Published - 1 Apr 2018

Keywords

Exponent
Induced subgraph
Primitive

Access to Document

10.1016/j.laa.2017.02.004

Cite this

@article{7ac962dd044b4ffda829be2f96bf137d,

title = "Edge-minimal graphs of exponent 2",

abstract = "A simple undirected graph G has the me2-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. This article considers graphs that can be embedded as induced subgraphs of me2-graphs by the introduction of additional mutually non-adjacent vertices and suitably chosen edges. The main results concern such embeddings of trees.",

keywords = "Exponent, Induced subgraph, Primitive",

author = "Olga O'Mahony and Rachel Quinlan",

note = "Publisher Copyright: {\textcopyright} 2017 Elsevier Inc.",

year = "2018",

month = apr,

day = "1",

doi = "10.1016/j.laa.2017.02.004",

language = "English",

volume = "542",

pages = "66--83",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Edge-minimal graphs of exponent 2

AU - O'Mahony, Olga

AU - Quinlan, Rachel

PY - 2018/4/1

Y1 - 2018/4/1

N2 - A simple undirected graph G has the me2-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. This article considers graphs that can be embedded as induced subgraphs of me2-graphs by the introduction of additional mutually non-adjacent vertices and suitably chosen edges. The main results concern such embeddings of trees.

AB - A simple undirected graph G has the me2-property if every pair of distinct vertices of G is connected by a path of length 2, but this property does not survive the deletion of an edge. This article considers graphs that can be embedded as induced subgraphs of me2-graphs by the introduction of additional mutually non-adjacent vertices and suitably chosen edges. The main results concern such embeddings of trees.

KW - Exponent

KW - Induced subgraph

KW - Primitive

UR - https://www.scopus.com/pages/publications/85013812774

U2 - 10.1016/j.laa.2017.02.004

DO - 10.1016/j.laa.2017.02.004

M3 - Article

SN - 0024-3795

VL - 542

SP - 66

EP - 83

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

ER -

Edge-minimal graphs of exponent 2

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this