Tagged Questions
1
vote
1answer
54 views
Anonymous graphs and graph embeddedness
What are anonymous graphs, what is graph embeddedness, and how do they relate to each other? Very confused - I could not find short answer. Thanks.
1
vote
0answers
42 views
Which cut does the “minimum cut” refer to?
My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
2
votes
0answers
34 views
Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?
I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book.
Which does "cut" most commonly refer to?
p.s. I am aware that "cut" itself can be defined to ...
1
vote
1answer
44 views
Prüfer sequence for an order-2 tree?
All the algorithms for constructing a Prüfer sequence state that the input is a tree, but none give any output corresponding to an order-2 tree.
And Wikipedia gives this definition:" A Prüfer ...
3
votes
1answer
23 views
What is the name for the unique “simplification” of a graph?
Is there a conventional name for the resultant graph (H) obtained by deleting all loops and multiple edges from the original graph (G)?
Something along the lines of "Let H be the simple graph of G.." ...
2
votes
1answer
39 views
how to write the process of decomposition of a graph into shortest closed sub graphs
If I want to decompose a graph in to possible shortest closed cycles (as shown in right side).
then how can i describe this process with mathematical notations.
to understand please refer below ...
0
votes
1answer
44 views
Mathematical notation of graph subdivision
If anyone can define a directed graph subdivision with mathematical notation, please post a response.
My second question is: Irrespective from the planar embedded graph or not, is this
definition ...
1
vote
1answer
49 views
What is the graph $K^c_m$?
The book "Graph Theory with applications" by J.A. Bondy and U.S.R. Murty, which is available here. The Theorem $4.6$ of this book says that:
If $G$ is a non-Hamiltonian simple graph with $n≥3$ ...
0
votes
1answer
44 views
Operations with planar graphs
I think in the graph theory operations such as decomposition into cycles, union, intersection, difference, subdivision can be done.
If I am given a planar graph (for e.g. see figure), then can the ...
3
votes
0answers
51 views
Define composition of small cyles and making a big graph
I am having following sub graphs and wish to compose all and make a
one bigger graph (say G). After that, I want to select the closed path
where it is passing along the outer vertices of that ...
0
votes
1answer
64 views
Different formulation of a Traveling Salesman Problem
Given a undirected, weighted, complete graph $(V,E,c)$ with $c \to \mathbb{N}$ and $v_0 \in V$ we are looking for a set $E' \subset E$ minimal with respect to $c$ with the following conditions:
for ...
1
vote
1answer
48 views
How do we distinguish “walks” or “paths”?
For example, let $G(V,E)$ be a graph such that $V=\{v_1,v_2\}$ and $E=\{(v_1,v_2)\}$. And let $s_1:\{1,2\}\rightarrow V$ be a walk such that $s_1(1)=v_1$ and $s_1(2)=v_2$. And let ...
0
votes
1answer
41 views
What is this matrix called?
Let $G=(V,E)$ be a finite graph where $V$ has $n$ elements so that $V=\{v_1,...,v_n\}$.
Now, define $a_{ij}$ to be 1 if $(v_i,v_j)\in E$ and 0 otherwise. What is this $n\times n$ matrix $(a_{ij})$ ...
1
vote
1answer
57 views
Does *pair* always mean a pair of distinct elements in graph theory?
Definition of edge in wikipedia: An edge of a graph is a set of 2-elements in a set of vertices.
Definition of tournament in my text: A tournament is a directed graph such that each pair of vertices ...
1
vote
1answer
109 views
Definition of induced cycle
According to Diestel (page 4):
"If $G' \subseteq G$ and $G'$ contains all the edges $xy \in E$ with $x, y \in V'$, then $G'$ is an induced subgraph of $G$"
According to Wikipedia
"induced cycle is a ...
2
votes
0answers
69 views
Graph Theory: Help with a definition
I need some help to see if the definition I found of Cycles and Cycles Decomposition is right, here it is:
A graph is a Cycle if it is isomorph to another graph $G=(V,E)$ with the following ...
2
votes
1answer
108 views
bipartite graph - sufficient and necessary conditions
Sorry for a silly question, I got confused with the definition of bipartite graph.
What is a necessary and sufficient condition for a bipartite graph.
...
1
vote
2answers
61 views
Number of Vertices of Graphs
So, I was looking at some graph theoretical stuff, more specifically Topological Graph Theory, and I had a question about the definition of graphs: is there usually a condition in the definition ...
1
vote
0answers
17 views
Definition of Chromatic class digraph of a m-coloured digraph
I have to prove that if $D$ is a m-coloured digraph, then $K(D) = K\big(C(D)\big)$
Where $C(D)$ is the chromatic transitive closure of $D$, which is a multidigraph with the same nodes and arcs of $D$ ...
3
votes
0answers
49 views
Defining a Certain Class of Plane Graphs
I'm having problems finding the right words to formulate the following class of graphs in a definition. I'm defining a class of plane graphs with the following properties:
Removing any vertex of ...
5
votes
1answer
318 views
Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.
I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
1
vote
1answer
189 views
What is the definition of an induced cut
I am reading A simple min-cut algorithm (Stoer & Wagner, 1997), and the proof uses some terms I don't understand.
Specifically I am unclear on what is meant by "$C_v$ the cut of $A_v \cup \{v\}$ ...
2
votes
1answer
39 views
Reducts of categories
There are several ways to reduce a category. The skeleton of a category is the category with isomorphic objects collapsed into one i.e. the only isomorphisms that remain are the identities.
What's ...
1
vote
1answer
103 views
What does unique “minimal” partition mean (Context: Partitioning of Vertex-Sets)?
I am studying R. Diestel's Book Graph Theory and I encountered a formulation which I don't quiet understand. Mr. Diestel speaks in this proof on page 180 (Google Books Link) in the second last line of ...
1
vote
1answer
221 views
What is a “mixed graph”?
I'm working on a digraph problem in which bidirectional edges need to be treated separately. As such, we could consider them as undirected edges. Clearly, if I replace bidirectional edges with ...
1
vote
3answers
88 views
Should one think of a network as a connected graph ? (Or: What is the right way to think of a network?)
In the definition of a network, are we only considering connected graphs ?
Because I keep encountering definitions that don't assume explicitly that we deal with connected graphs, but which would be ...
6
votes
3answers
506 views
Is the empty graph connected?
Is the empty graph always connected ? I've looked through some sources (for example Diestels "Graph theory") and this special case seems to be ommited. What is the general opinion for this case ?
As ...
