21 lines
1.4 KiB
TeX
21 lines
1.4 KiB
TeX
%root: main.tex
|
|
|
|
We need all the possible edge patterns in an arbitrary $G$ with at most three distinct edges. We have already seen $\tri,\threepath$ and $\threedis$, so we define the remaining patterns:
|
|
|
|
\begin{itemize}
|
|
\item Single Edge $\left(\ed\right)$
|
|
\item 2-path ($\twopath$)
|
|
\item 2-matching ($\twodis$)
|
|
\item 3-star ($\oneint$)--this is the graph that results when all three edges share exactly one common endpoint. The remaining endpoint for each edge is disconnected from any endpoint of the remaining two edges.
|
|
\item Disjoint Two-Path ($\twopathdis$)--this subgraph consists of a two-path and a remaining disjoint edge.
|
|
\end{itemize}
|
|
|
|
For any graph $G$, the following formulas for $\numocc{G}{H}$ compute their respective patterns exactly in $O(\numedge)$ time, with $d_i$ representing the degree of vertex $i$ (proofs are in \Cref{app:easy-counts}):
|
|
\begin{align}
|
|
&\numocc{G}{\ed} = \numedge, \label{eq:1e}\\
|
|
&\numocc{G}{\twopath} = \sum_{i \in V} \binom{d_i}{2} \label{eq:2p}\\
|
|
&\numocc{G}{\twodis} = \sum_{(i, j) \in E} \frac{\numedge - d_i - d_j + 1}{2}\label{eq:2m}\\
|
|
&\numocc{G}{\oneint} = \sum_{i \in V} \binom{d_i}{3}\label{eq:3s}\\
|
|
&\numocc{G}{\twopathdis} + 3\numocc{G}{\threedis} = \sum_{(i, j) \in E} \binom{\numedge - d_i - d_j + 1}{2}\label{eq:2pd-3d}\\
|
|
&\numocc{G}{\threepath} + 3\numocc{G}{\tri} = \sum_{(i, j) \in E} (d_i - 1) \cdot (d_j - 1)\label{eq:3p-3tri}
|
|
\end{align} |