All Questions
8 questions
2
votes
1
answer
126
views
"Balanced" separator which is independent set
I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that
$S\subset V$ is a separator
for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....
- 91
3
votes
2
answers
406
views
What is the definition of brick product of graphs?
Can anyone help me with the exact definition of brick product of graphs, say path, cycle.
I am not able to find a paper with a clear definition on the internet. Can anyone give me a URL to such a ...
- 101
0
votes
0
answers
140
views
Graph theory: Closed neighourhoods and generalized clustering coefficients
The neighbourhood of node $v$ in graph $G$ is the subgraph of $G$ induced by all vertices adjacent to $v$.
The number of edges between neighbours divided by the number of pairs of neighbours is ...
- 9,720
1
vote
0
answers
337
views
What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?
Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph?
Update ...
- 1,826
3
votes
2
answers
138
views
In the context of directed graphs is it standard notation to allow an element of an independent vertex set to be contained in a loop?
Given any relation $R$, that is, any set of ordered pairs, we can associate a unique digraph $D$ to our relation $R$ by setting $D=(\text{fld}(R),R)$ where $\text{fld}(R)=\text{dom}(R)\cup\text{rng}(R)...
- 2,506
11
votes
0
answers
228
views
Is there a term for this graph subset?
Suppose $G$ is a (finite) graph which is $k$-vertex colourable (i.e. $\chi(G)\leqslant k$). Suppose $S$ is a set of vertices of $G$ with the following property:
If $c:V(G)\rightarrow [k]$ is a vertex ...
- 211
2
votes
1
answer
180
views
Graph algebras a la Lovasz
In the article (Lovasz, section 1.3) mentions graph algebra structures on the set of formal linear combinations (over a field?) of a collection of graphs. He also mentioned quantum graphs as an ...
- 271
12
votes
7
answers
769
views
Does the notion of graphs with vertex multiplicity exist?
I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have.
It is actually a way to write in a ...
- 222