1
$\begingroup$

I am having difficulties understanding what an adjacency matching according to the definition given in a paper.

An adjacency matching in an undirected graph G is a collection of disjoint edge pairs in G such that if two edges e and e' are paired, then e and e' share a common endpoint. A maximum adjacency matching is an adjacency matching with the maximum number of edge pairs.

Could anyone explain what an adjacency matching is according to this definition?

$\endgroup$
5
  • $\begingroup$ Do you understand the idea of a collection of disjoint pairs? $\endgroup$
    – hardmath
    Nov 10, 2015 at 4:29
  • $\begingroup$ Nope. Had trouble there too. This is what I think though. If we include two edges (as a pair) in the matching, then we can't include either of these edges in any other pair (or matching). Is that right? $\endgroup$ Nov 10, 2015 at 4:32
  • $\begingroup$ Yes, exactly. Now you are only allowed to use edges that are distinct from one another, yet share one endpoint, to make as many "disjoint pairs" as possible. That's a maximum adjacency matching, as defined in your quoted paper. $\endgroup$
    – hardmath
    Nov 10, 2015 at 4:55
  • $\begingroup$ Oh! Maximum is the most number of "disjoint pairs" that can be formed. Cool, thanks hardmath! $\endgroup$ Nov 10, 2015 at 4:58
  • $\begingroup$ It would make your Question a little bit better to cite (give title and author) the paper where this definition is found. $\endgroup$
    – hardmath
    Nov 10, 2015 at 13:41

1 Answer 1

0
$\begingroup$

First, an adjacency matching is defined for a simple undirected (finite) graph $G$ to be a disjoint collection of unordered pairs of (distinct) edges which share exactly one endpoint. Therefore an edge of $G$ can belong to at most one such pair in the collection.

Then a maximum adjacency matching is one that has the largest possible number of edge pairs. Finiteness of $G$ guarantees that the maximum number of pairs is attained by some adjacency matching.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .