Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
59 views

Find all 'big' cycles in an undirected graph

I am unfamiliar with graph theory and hope to get answers here. My goal is to find all 'big' cycles in an undirected graph. A 'big' cycle is a cycle that is not a part of another cycle. (Compare with ...
1
vote
0answers
60 views

Does every simple cycle contain at least one back edge?

Soppose we have an udirected, connected graph. Apply the DFS algorithm to find back edges of this graph. Now, I have found a lecture notes saying following : Each back edge (i,j) defines a cycle. A ...
1
vote
0answers
48 views

maximum number of pendant vertices in a graph

Can anybody help me in providing a simple hint to my problem. I was just thinking how many pendant vertices a graph can have where diameter of the graph, $diam(G)\geq3$, after leaving the graph $P_4$. ...
1
vote
0answers
92 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
0answers
38 views

Can a planar graph have multiple edges joining 2 vertices?

If they are planar, do the properties $2E \geq 3F$ and $E \leq 3V-6$ remain true? For example, consider 2 vertices joined by 2 non-intersecting edges. Then $E=2, F=2$ and $V=2$ and $2E \not > 3F$. ...
1
vote
0answers
49 views

“Let $G$ be a planar graph. Show that every pair of vertex-disjoint odd cycles in $G^c$ is connected by an edge.” Can't figure out why “odd” matters.

If $C_1,C_2$ are vertex-disjoint cycles in $G^c$, of lengths $m,n$ respectively, not connected by an edge, then their complement has a $K_{m,n}$ minor with $m,n\geq 3$, so $G$ contains $K_{3,3}$ as a ...
1
vote
0answers
69 views

maximum weight on a directed graph (weighted)

I have a problem in finding an algorithm for matching of maximum weight on a directed graph (weighted). In particular, I would also need to find all the matching induced by subgraphs of the given ...
1
vote
0answers
28 views

Conservativeness on a graph

I'm trying to build a conservative vector field out of something smaller than $\mathbb{R}^2$ to understand how the "conservative" property of differences-of-scalar-fields leads to Green's theorem. (In ...
1
vote
0answers
75 views

How many London underground stations you can visit without passing through the same station twice?

If you can start anywhere and only travel on the lines shown in the official map (http://www.tfl.gov.uk/assets/downloads/standard-tube-map.pdf) (including overground, DLR, Emirates Air Line and ...
1
vote
0answers
15 views

Reweight a graph to give it a small max cut

Let $G = (V, E)$ be an undirected, unweighted graph. I wish to assign weights (possibly negative, not all zero) to the edges to minimize the value of: $$\frac{m}{\|w\|}$$ where $m$ is the value of ...
1
vote
0answers
52 views

Improved approximation algorithm for maximum weighted matching

I've read the discussion here: http://stackoverflow.com/questions/5203894/a-good-approximation-algorithm-for-the-maximum-weight-perfect-match-in-non-bipar, and I have implemented the Drake and ...
1
vote
0answers
36 views

Let G=(V,E) be a K1,3- free graph

Let $G=(V,E)$ be a $K1,3\mbox{-}$ free graph. Show that there exists a maximal fixed set $S⊆V$ in relation with the inclusion with the property that for every set of vertices $T⊆V$, where $∀v ∈ V − ...
1
vote
0answers
37 views

Convert graph of triangles into edges for the sake of coloring

I have graph made of triangles, and i need to color triangles. But i already have algorithm to color edges. Is there any known algorithm to convert graph in a way to correspond edge <-> triangle? ...
1
vote
0answers
17 views

Can a circuit in graph theory use a edge twice in the circuit

I need to find out a circuit in a graph that uses the edge ab, what I want to know is can the circuit use the edge ab, more than once.
1
vote
0answers
31 views

Maximization problem on a graph

Consider a graph $G(V,E)$. Let degree of each vertex be denoted to $\beta(v) < d$. Maximize the following, where $\beta(v)$ is the only variable for all vertex $v\in V$. $$ \max \sum_{(u,v)\in E} ...
1
vote
0answers
205 views

Is D.B.West's Introduction to Graph theory a good book to start?

I am studying for International Olympiad for Informatics (IOI) and I have to have a good understanding of Graph Theory . a teacher suggested reading Introduction to Graph Theory by D.West. Is it a ...
1
vote
0answers
49 views

applications of product graphs

I was reading a book http://imrich.at/books/handbook-of-product-graphs-second-edition/. Under the section Preface it was written that: large networks such as the Internet graph, with several ...
1
vote
0answers
42 views

Family of sets. Directed acyclic graph representation.

We are given a family of sets $F=\{F_1,\ldots,F_n\}$ with each $F_i$ being a subset of a ground set $N=\{1,\ldots,n\}$. In addition, we assume for each $F_i$ that it's not the subset of another $F_j$ ...
1
vote
0answers
45 views

Kruskal-Katona Theorem with Majority?

I am interested in the following problem which seems like an extension of the Kruskal-Katona Theorem. Let $A_k \subseteq \{0,1\}^n$ be a subset of the hypercube such that every element in $A$ has ...
1
vote
0answers
28 views

Polynomial-Reduction (Clique)

If we define the language 2CLIQUE = {(G; t) | G is a graph with at least 2 di fferent cliques of size t}. Now if 2CLIQUE ∈ P then CLIQUE should be ∈ P? I need a bit of help understanding this.
1
vote
0answers
141 views

Does this graph operation have a name? Subgraph join?

Given a graph $G$ and two of its subgraphs $A$ and $B$ we define another subgraph, $A+B\subseteq G$ as the subgraph with the following properties, The vertex set of $A+B$ is the union of the vertex ...
1
vote
0answers
75 views

Complete tripartite graph hamiltonian

Let $G_{a,b,c}$ be a complete tripartite graph. For what values of $a, b$ and $c$ is $G_{a,b,c}$ Hamiltonian?
1
vote
0answers
46 views

Subgraph without “holes”

does everyone know, if there already exists a definition of subgraphs, which do not contain a "hole"? EDITED: That means: I presuppose a planar embedding of a graph G and I want to find a connected ...
1
vote
0answers
118 views

Are there necessary and sufficient conditions of a graph to decompose into two Hamiltonian cycles?

Let $G$ be a graph. Definition: $G$ is decomposable into two Hamiltonian cycles if the edge set $E(G)$ can be partitioned into two disjoint Hamiltonian cycles. Obviously, if $G$ is decomposable into ...
1
vote
0answers
55 views

Prove that a finite complete graph can be embedded in $\mathbb{R}^3$

I've actually found a few intuitive examples where edges are taken to a twisted cubic and and the vertices are arranged in a certain way and that's very nice, but I'm actually more interested in a ...
1
vote
0answers
44 views

Intuitive understanding of 'Graph Limits'

I've been trying to understand the concept of Graph Limits (In particular, the following paper by Lovasz 'Limits of dense graph sequences') for a particular project of mine. I'd like to know if ...
1
vote
0answers
68 views

Digraphs: Is this an example of a digraph with no cycles, but a closed walk?

I'm trying to apply this vocabulary: cycle and closed walk on a digraph. So since a cycle is a walk such that all the vertices are different except the last two, and a closed walk is just a walk that ...
1
vote
0answers
63 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
48 views

regular graph (dividing vertices togroups of edges and circles)

Let G be a regular graph. Prove that it's vertices can be divided to groups of either edges or circles. Assuming we are looking at a K-regular graph, I was testing the effect of K being odd or even. ...
1
vote
0answers
42 views

fitness cost calculation finding the weighted sum

I am having a little bit of trouble making a weighted sum calculation for subpaths(Where subpath is the path between two cities e.g. A->B) in a travelling salesman problem. Basically I have 3 ...
1
vote
0answers
154 views

relationship between kruskal algorithm and TSP

Question $8$: Is the TSP tour obtained in Question 7 optimal? For question $6$, I got total weight is 60. Edges are $1-2, 2-4, 3-4, 3-9, 5-6, 6-7, 7-8, 8-9$ Question $7$: We need to add the edge ...
1
vote
0answers
47 views

Isomorphisms from $K_5$ to points in $\mathbb R^4$

Is there an isomorphism from the complete graph $K_5$ to a triangular solid in $\mathbb R^4$? For example $K_3$ is trivially mapped to a triangle, $K_4$ may be mapped to a tetrahedron, so what about ...
1
vote
0answers
123 views

Number of paths through an incomplete graph (with restrictions)

Here's a question I came upon while fiddling around with yarn on spindles. I joined three spindles so that they were orthogonal.. then, beginning at the base of a particular spindle (A), wound it ...
1
vote
0answers
41 views

On graph homomorphism properties

Let $G,H$ be finite graphs with $|V(H)| > |V(G)|$. Let $\mathcal{f}:G\rightarrow H$ be an injective homomorphism - that is, $\mathcal{f}$ is: $1.$ Injective - ...
1
vote
0answers
277 views

How to show that union and intersection of min cuts in flow chart is also a min cut

The proof of this is everywhere skipped and said to be collorary of Ford-Fulkerson theorem. It's usually something like: Let $A$ and $B$ be low cuts of a flow chart. Then $A \cup B$ and $A \cap B$ ...
1
vote
0answers
46 views

What does it mean for two graphs to be consistent

I am trying to understand what does it really means for two graphs to be consistent in the context of bidirectional transformation ? Can you provide me with a good example? Thank you in advance.
1
vote
0answers
26 views

Terminology for a graph that can be drawn in several planes?

A graph is called planar if you can draw it in the plane without any edges crossing. In circuit layouts, it's common to try to lay out a graph across multiple different planes, where edges can jump ...
1
vote
0answers
57 views

Mathematical research on ground state configuration of ising model

I want to do mathematical research (algorithm construction and mathematical analysis) on ising model ground state configuration. From what I know, the state of art research is using graph theory ...
1
vote
0answers
81 views

Graph theory name for minimum depth to leaf node.

In a graph theory rooted tree, is there a name for the minimum depth downwards to reach a leaf node? I have in mind calculating "depth to a leaf" at each node by looking downwards through the subtree ...
1
vote
0answers
91 views

Odd problem about graph connectivity

This problem asks how to prove that a graph has k-connectivity. However, there's something which makes the problem intricate. The graph which I'm studying about is a graph with 2k-2 vertice and the ...
1
vote
0answers
62 views

Recommend an intro to binary embedding algorithm in Graph Theory

I'm working on my final year project which will establish an reasonable upper bound for one of the bandwidth problem in graph theory. I found difficulty on understanding an algorithm that construct an ...
1
vote
0answers
33 views

Graphs: First Order Characterisation Of A path

Whilst reading this: http://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdf a seminar on finite model theory, I thought that something was wrong. "Given a Graph G and a Binary ...
1
vote
0answers
20 views

Determine the multiplicity of knots for a graph

Here are my two questions: Given a finite connected non-oriented planar graph, is there a way to determine whether or not it is possible to derive a single non-trivial knot diagram from this graph, ...
1
vote
0answers
121 views

Node mapping with edge weights

For an academic paper, I wish to use node mapping and weighted edge. I do not understand the concepts quiet clearly. I have a weight on each edge. The graph for which am trying to solve the problem ...
1
vote
0answers
74 views

“Das ist das Haus vom Nikolaus” and Euler cycle

Consider the following graph $(V,E)$: With $a, b, c, d, e \in V$. Then I obviously can make an Euler cycle: $[b, a, c, e, d , c, b, e, a]$. But it also holds that $deg(a)=deg(b)=3$ which is not ...
1
vote
0answers
48 views

automorphism of a rooted tree

Nowadays i'm working with tree automorphisms. I couldn't find information about rooted tree automorphism concerning the root. Does an automorphism of a rooted tree fix the root or not? Logically it ...
1
vote
0answers
133 views

prove matroid conditions

can anybody please help me to prove bicircular matroid is a matroid, from the direct definition of bicircular graph, it is also called pseudoforest. So we define the independent set to be the edge ...
1
vote
0answers
56 views

Types of symmetry for combinatorial graphs

Let $G$ be an undirected, connected graph without loops. Let's call $G$ symmetric iff it has a non-trivial automorphism (that is a permutation $\pi : V(G) \rightarrow V(G) $ – which is not the ...
1
vote
0answers
83 views

Expected distance traversed between 2 vertices on probabilistic graph

Let $V = \{1,2,3,...,N\}$ be the vertex set of a graph. Let $d(i,j)>=0$ represent the $(i,j)$ vertex distance between vertices $i$ and $j$, $i \in V, j \in V$. Now, define a non-negative number ...
1
vote
0answers
33 views

Embeddings and Covering faces?

I have a dude with the following problem. Suppose you have an 2-cell embedding of some simple graph $G$ on a orientable type surface $S_g$ (for example a plane graph), and you desire to find a set $A ...