« first day (2685 days earlier)      last day (99 days later) » 

12:14 AM
A new tag was created by Rodrigo de Azevedo, including a tag-excerpt.
Q: How does an adjacency matrix represent a weighted multigraph?

jeshwanth chowdaryI 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?

Q: Difference between graph and multigraph

Intellectual_ 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?

Q: What is the edge set of a multigraph?

Conor O'BrienAn 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...

Q: Directed multigraph with numbered edges

portonLet 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...

Q: Line Graph of Multigraph

M.BadaouiThe 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...

Q: Bridge in a multigraph

Craig FeinsteinAccording 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...

Q: Clarification on the definition of multigraph

Sook LimIf 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.

Q: Topological sort of a subgraph of a multigraph

wyer33Is 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 -->...

Q: Existence of a multigraph

KimI'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...

Q: What is the name of a set of parallel edges in a multigraph?

Jim NewtonIn 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.

Q: Prove the edges of a multigraph may be oriented such that the net-degree of any vertex is $\leq 1$.

Daniel PietrobonThe 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...

Q: Perfect Matchings in Biclique Decompositions of Multigraphs

Richardsuppose you have the $K_{2n}$ covered by a multigraph consisting of $2n-1$ bicliques, each consisting of a partition of the vertex set into two sets of equal size. Here is a picture of $K_{6}$ with 5 bicliques. My question is: under which circumstances is it possible to pick a perfect matchi...


« first day (2685 days earlier)      last day (99 days later) »