Maximum Adjacency Order

an ordering of vertices (𝑣₁, 𝑣₂, …, 𝑣_𝑛) in an edge-weighted graph (𝐺, 𝑤) is called a maximum adjacency ordering if it satisfies:

𝑑_(𝐺,𝑤)({𝑣₁, 𝑣₂, …, 𝑣_𝑖-1}, 𝑣_𝑖) ≥ 𝑑_(𝐺,𝑤)({𝑣₁, 𝑣₂, …, 𝑣_𝑖-1}, 𝑣_𝑗) # for 2 ≤ 𝑖 ≤ 𝑗 ≤ 𝑛

where:

• 𝑑_(𝐺,𝑤)(𝑋,𝑌) denotes Σ{𝑤(𝑒) | 𝑒 = {𝑥,𝑦}∈𝐸, 𝑥∈𝑋, 𝑦∈𝑌}

Theorem - Nagamochi & Ibaraki

In any MA ordering of vertices, the following statement holds:

𝜆(𝑣_𝑛−1, 𝑣_𝑛) = 𝑑(𝑣_𝑛)

where:

• 𝑑(𝑣) denotes the degree of the vertex 𝑣
• 𝜆(𝑢, 𝑣) denotes the edge-connectivity between vertices 𝑢 and 𝑣