I heard that each element $a(i,j)$ of the matrix either represents the degree from vertex $i$ to vertex $j$ or does it represent the weight?
Does there exist a multigraph $G$ of order $8$ such that the minimal $d(G) = 0$ while maximal $d(G) = 7$? What if ‘multigraph $G$’ is replaced by ‘graph $G$’? Answer: such multigraph does not exist, but graph?
An edge set of a graph is a set of doubletons, pairing edges. For example: has an edge set of $\{\{6,4\},\{4,5\},\{4,3\},\{5,2\},\{5,1\},\{3,2\},\{1,2\}\}$. A set, by definition, cannot have duplicate elements, else it is not a set. is a multigraph. All graphs have edge sets, yet the edge s...
Let we have a directed multigraph such that or every its vertex the set of edges from this vertex is finite and ordered (in other words, numbered $1,\dots,n$). I need this construct to describe (depth-first or breath-first) traversing this directed multigraph (where edges are iterated in the abo...
The answer to this question could be trivial! The line graph of simple $d$-regular graph is ($2d-2$)-regular, since each edge is connected to $d-1$ edges for each of its two vertices. My question is the line graph of regular multigraph is also regular graph? I think that only the loops coul...
According to Wikipedia: [...] a bridge in an undirected graph is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. Suppose I have a multigraph $G = (V,E)$ with two vertices $u,v \in V$ with...
If I have a graph that has an edge that straight connects vertice $A$ to $B$ and another that connects vertice $A$ to $C$ then to $B$ is it considered a multigraph? Clarification will be much appreciated. Thanks.
Is there a good algorithm for doing a topological sort of a subgraph of a multigraph? More specifically, given a multigraph G and a node n in the graph. Consider the subgraph G' all the nodes reachable from n in G. Is there a good way to find a topological sort of G'? For example A --> B -->...
I'm an undergraduate student majoring in mathematics. I'm solving my home assignment and got stuck at this problem. Suppose $d_1\geq d_2\geq\dots \geq d_n\geq 1$ and $\sum_{i=1}^nd_i$ is even. Prove that there is a multigraph with degree sequence $d_1, d_2, > \dots, d_n$ if and only if $d_1...
In directed multigraph, two vertices, $a$ and $b$, may have zero or more parallel edges connecting them in one direction or the other. Does this set of parallel edges have a name? I seem to remember reading a book which gave this set a name.
The net-degree of a vertex $v$, denoted $\text{netdeg}(v)$, in a digraph $G$ is defined by $$ \text{netdeg}(v)=| ~ \text{outdeg}(v) - \text{indeg}(v) ~| $$ where $\text{outdeg}(v)$ and $\text{indeg}(v)$ are the out-degree and in-degree of $v$. Show that the edges of any multigraph may be orien...
« first day (2685 days earlier) ← previous day next day → last day (1664 days later) »