Questions tagged [multigraphs]

A multigraph is a graph that can have multiple edges with the same end nodes. Thus, two vertices may be connected by more than one edge.

Filter by
Sorted by
Tagged with
0
votes
0answers
10 views

Why do the vertices in the resulting multigraph have even degree?

Suppose G(V,E) is a multigraph(i.e. we can have parallel edges in the graph) which contains a cycle C and for all vertices $v \in V$ we have that $deg(v)$ is even. Now suppose that we remove C from G ...
0
votes
1answer
30 views

Can a simple graph have weighted edges?

Can a simple graph have weighted edges or is it a multigraph as soon as it has weights? To me it seems like the adjacency matrix would look the same (as from a multigraph). Also I thought I had read ...
1
vote
0answers
31 views

How to read the mathematical notation for multigraphs?

How to read the mathematical notation for multigraphs: $$E \rightarrow V \cup[V]^2 $$ $E$ is a set of edges $V$ is the set of vertices I am having trouble especially with this part $$[V]^2 $$ ...
0
votes
0answers
25 views

All possible manipulations of multigraphs?

does anyone knows a paper/book, listing all possible simple manipulations of multigraphs? Like adding an edge here or removing a node there. I'd like to run an induction proof on all those cases, so i ...
1
vote
1answer
45 views

Disjoint cycles in a regular multigraph of even degree

Does a regular multigraph of even degree possess a set of cycles containing each vertex precisely once? [In a regular multigraph every vertex has the same degree. No loops are allowed but more than ...
1
vote
0answers
28 views

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

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 ...
1
vote
1answer
52 views

Partition edges of multigraph

Given a connected multigraph $ G = (V,E) $ show that if $d_G(x)$ is not even $\forall x \in V $ or $|E|$ is even there exists a partition of $E = A $ $\cup$ $B$ such that: $|d_A(x) - d_B(x)| \leq ...
0
votes
2answers
600 views

How does an adjacency matrix represent a weighted multigraph?

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?
0
votes
0answers
179 views

Degree sequence multigraph without loop

I am trying to prove the following $d_n$ is a degree-sequence of the multigraph $G$ (without loops) if and only if $\sum_{i=1}^{n}{d_i}$ is even and $d_1 \le\sum_{i=2}^{n}{d_i}$ I have no ...
0
votes
3answers
93 views

Clarification on the definition of multigraph

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 ...
2
votes
1answer
66 views

Existence of a multigraph

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. ...
2
votes
1answer
272 views

Line Graph of Multigraph

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 ...
0
votes
0answers
238 views

Multigraph definition confusion

I've started Graphs, Algorithms, and Optimizaton by Kocay and Kreher. They describe a multigraph as having more than one edge between the same end point vertices. . . . . . an edge can then no ...
4
votes
2answers
4k views

What is the edge set of a multigraph?

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 ...
3
votes
1answer
5k views

Directed Multigraph or Directed Simple Graph?

I have the following two questions in my book: Question # 1 Determine whether the graph shown has directed or undirected edges, whether it has multiple edges, and whether it has one or more loops. ...
3
votes
0answers
438 views

Directed multigraph with numbered edges

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 (...
2
votes
0answers
50 views

Perfect Matchings in Biclique Decompositions of Multigraphs

suppose 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 ...
2
votes
1answer
859 views

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

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}(...
1
vote
0answers
339 views

Topological sort of a subgraph of a multigraph

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 ...
0
votes
1answer
1k views

Difference between graph and multigraph

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, ...
2
votes
0answers
207 views

Bridge in a multigraph

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