All Questions
19 questions
0
votes
0
answers
102
views
Merging two composable walks in a graph
Let $G$ be a graph (i.e., an undirected graph in which we allow for loops and parallel edges). Denote by $V$ the vertex set, by $E$ the edge set, and by $\psi$ the incidence function of $G$, and let $\...
- 10.5k
1
vote
0
answers
72
views
Another betweenness centrality measure: neighbourhood centrality
Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind).
Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...
- 9,720
7
votes
2
answers
637
views
Line graphs called "graph derivatives": any intuition?
Short version: in several papers, line graphs (and closely related graphs) are called graph derivatives or derived graphs; is there any intuition for such terminologies, in connection with the ...
- 1,444
1
vote
0
answers
35
views
Term or reference for a set of integer edge weights to guarantee distinct weighted degrees
I am looking for a term or reference describing sets $S$ of $\binom{n}{2}$ non-negative integers such that, for every bijection $w: E(K_n)\to S$ and every pair of distinct vertices $u$ and $v$ in $V(...
- 11
7
votes
0
answers
74
views
Graphs all of whose cuts are positive
Let $(V, E, w)$ a weighted graph, with vertices $V$, edges $E$, and signed weight $w:E\to \mathbb R$.
I am interested to know other popular properties that are known to imply, or are equivalent to, ...
- 2,041
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
2
votes
0
answers
124
views
Graphs which are built from complete graphs : Reference request
Let $V$ be a set of $n$ vertices. Fix $3 \le k \le n$. Let $\binom V k$ be the set of all $k$ element subsets of $V$.
We add the edges in $V$ as follows: Let $\mathcal S \subseteq \binom V k$ be ...
- 1,269
3
votes
0
answers
346
views
Terminology for transforming a directed acyclic graph into a tree
I am looking for the term of converting a directed acyclic graph (DAG) into a tree by traversing its topologically ordered nodes and copying the subtrees of the nodes with in-degree $> 1$.
Such a ...
- 265
3
votes
1
answer
223
views
Yet another graph characteristic
I wonder if the following graph-theoretical concepts have been considered before, and if so, under which name.
Consider a directed graph $G$ with $n$ nodes.
Let the cycle number $\gamma(\nu)$ be ...
- 9,720
6
votes
1
answer
305
views
Name of a binary matroid coming from the cycle space of a graph
In some of my recent work, I have 'discovered' a binary matroid which I will describe below.
Given a graph $G$, let $H_1(G, \mathbb{Z}/2\mathbb{Z})$ denote the cycle space. This is a vector space ...
- 291
0
votes
1
answer
62
views
Standard names of two finitary properties of hypergraphs?
Now we are writing a paper on minimal covers and minimal vertex-covers in hypergraphs and would like to know if there are any standard names for the following two (dual) properties of a hypergraph $(V,...
- 41.9k
0
votes
0
answers
307
views
Graph Coloring: Two adjacent vertices share same color
Consider, subgraphs $G_1, G_2,...... G_x$ of graph $G$. Each subgraph has $k$ vertices.
Now, Fix subgraph $G_1$ and consider another subgraph $G_k$ where $1 <k \le x$.
The edge set ...
- 267
1
vote
2
answers
122
views
Maximal Minimum Weight DAGs
In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well ...
- 13.2k
3
votes
1
answer
606
views
Node-edge coloring of graphs
There must be work on this concept, but I am not finding it through
searches, perhaps using the wrong terminology.
Define a node-edge coloring of a graph $G=(V,E)$...
- 151k
4
votes
2
answers
297
views
What is the standard name of an edge-graph
Given a graph $G=(E,V)$, I construct a graph $G'$ where the vertices of $G'$ are given by the edges of $G$ and say that two edges of $G$ are neighbors in $G'$ if they have a common vertex.
Is there a ...
- 71
4
votes
3
answers
2k
views
Term for "Directed acyclic graph with exactly one sink and one source"
There's a theorem/lemma that states that a finite directed acyclic graph (DAG) has at least one sink and at least one source. Is there a term for a (finite) DAG with exactly one sink and one source?
...
- 2,235
4
votes
3
answers
410
views
Name of an operation on graphs
I asked this a week ago on math.SE, but haven't obtained an answer yet, so I hope it is fine to ask this here too.
Let $G$ and $H$ be two possibly directed, non necessarily simple, vertex-labelled ...
- 1,164
10
votes
3
answers
1k
views
What is this operation on graphs called?
I am currently studying certain infinite graphs in terms of their finite induced subgraphs.
For the graphs that I am interested in the class of finite induced subgraphs is closed under the following ...
- 16.2k
3
votes
2
answers
259
views
Have this subclass of split graphs been studied before?
I am interested in the properties of the following subclass of split graphs:
The class consists of all split graphs $G=(C\cup I)$ where $C$ is a clique and $I$ an independent set, and every pair of ...
- 185