Definition of the Transversal of a Graph

Question

Basic definition question that seems hard to find. Can someone provide me the definition for a transversal of a graph $G=(V,E)$? Specifically, I am considering bipartite graphs.

Answer 1

In combinatorics in general, given a family of sets $\mathcal S = \{S_1, \dots, S_n\}$, a transversal $T$ of $\mathcal S$ is a set with the property that $T \cap S_i \ne \varnothing$ for all $i$. (Often but not always, we require that $|T \cap S_i|$ be exactly $1$ for all $i$.)

There are plenty of graph-theoretic problems in which transversals come up; for example, any cut in $G$ is a transversal of the set of spanning trees of $G$ (considered as sets of edges).

If this is the definition you're looking for, then without knowing what set family you're thinking about to begin with, there's no more specific definition of what a transversal is.

Answer 2

Do you mean graph traversals? Or transversals in bipartite graphs?

Given a bipartite graph $G$ with bipartition $V(G)=X \cup Y$, a transversal in $G$ is a set of $|X|$ independent edges (ie a complete matching from $X$ to $Y$). A transversal is also called a system of distinct representatives (SDR) because the bipartite graph can be viewed as representing a set system, with the vertices of $X$ correspond to the subsets. Hall's marriage theorem asserts that the obvious necessary condition for a graph to have a transversal is also sufficient.

Graph traversals methods visit each vertex of the graph exactly once. Examples of graph traversal algorithms are BFS (breadth first search) and DFS (depth first search).