The proper diameter of a graph | Zendy

Vincent E. Coll | Zendy; Jonelle Hook | Zendy; Colton Magnant | Zendy; Karen McCready | Zendy; Kathleen Ryan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The proper diameter of a graph

Author(s) -

Vincent E. Coll,

Jonelle Hook,

Colton Magnant,

Karen McCready,

Kathleen Ryan

Publication year - 2018

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.2115

Subject(s) - combinatorics , mathematics , colored , edge coloring , graph coloring , graph , path graph , graph power , fractional coloring , complement graph , discrete mathematics , line graph , materials science , composite material

A proper edge-coloring of a graph is a coloring in which adjacent edges receive distinct colors. A path is properly colored if consecutive edges have distinct colors, and an edge-colored graph is properly connected if there exists a properly colored path between every pair of vertices. In such a graph, we introduce the notion of the graph’s proper diameter—which is a function of both the graph and the coloring—and define it to be the maximum length of a shortest properly colored path between any two vertices in the graph. We consider various families of graphs to find bounds on the gap between the diameter and possible proper diameters, paying singular attention to 2-colorings.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research