0
$\begingroup$

I am reading Decompositions of Triangle-Dense Graphs by Gupta et al.

On page 2, in Definition 1 what is a wedge in a graph?

I know what triangle is but I don't know what wedge is and google isn't helping!

$\endgroup$
6
$\begingroup$

They say it in the paper.

Let a wedge be a two-hop path in an undirected graph.

So it is a path with 2 edges, like 2/3 of a triangle.

$\endgroup$
0
3
$\begingroup$

Right before the definition the authors define a wedge to be a two-hop path in an undirected graph. After the definition, they note that every triangle of a graph contains 3 wedges. In other words, with a wedge they mean a path $P_3$.

$\endgroup$
5
  • $\begingroup$ Or $P_2$, depending on whether you name your paths after the number of edges or number of vertices they contain. Isn't it more common to count the edges? $\endgroup$ – David Richerby Feb 9 '14 at 19:53
  • $\begingroup$ @DavidRicherby It's definitely more common to count the vertices. Similar notation is used e.g. for complete graphs, cycles, stars and wheels ($K_n$, $C_n$, $S_n$, $W_n$). This way it's more natural to define small graphs (think of say $P_1$). Also, it's not that easy to specify say wheels or complete graphs by edge count. $\endgroup$ – Juho Feb 10 '14 at 9:17
  • $\begingroup$ Are you sure it's more common for paths? All the graph theory books on my shelf (Bollobas, Modern Graph Theory; Diestel, Graph Theory; and Hell and Nesetril, Graphs and Homomorphisms) define a $k$-path to have $k$ edges and $k+1$ vertices. $\endgroup$ – David Richerby Feb 10 '14 at 14:08
  • $\begingroup$ @DavidRicherby I'd say so yes, at least if the notation is precisely $P_n$ (Diestel seems to use $P^k$, where $k$ stands for the number of edges). ISGCI uses $P_3$ to mean a path on 3 vertices, as does Wolfram MathWorld and Wikipedia. $\endgroup$ – Juho Feb 10 '14 at 14:56
  • $\begingroup$ Yeah, Diestel uses $P^k$, $K^k$ etc. so he can write things like "Let $P_1, \dots, P_k$ be the $k$ distinct paths between $S$ and $T$." $\endgroup$ – David Richerby Feb 10 '14 at 15:03
0
$\begingroup$

A nice and easy explanation of wedges is available the paper "Triadic Measures on Graphs: The Power of Wedge Sampling" SDM, 2013.

$\endgroup$
1
  • $\begingroup$ Welcome to the site! Given that a wedge is just a 2-path, I'm not sure much more explanation is needed. :-) But please give a full citation and a link to the paper, in any case. $\endgroup$ – David Richerby Nov 28 '16 at 8:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.