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
36 views

Number of Isolated Edges in G(n,p)

I am attempting to find the number of isolated edges in the Erdos - Renyi graph G(n,p). I need to find the formula for the expected number of isolated edges. I've broken the equation down into ...
1
vote
0answers
37 views

Determine the condition on $n$ for $W_n$ to be critical graph.

The way my professor defines $W_n$ is the wheel graph of $n + 1$ vertices. That is, the graph with $n$ vertices, each adjacent to the vertex of degree $n$, in the cycle. We assume $W_n$ is a simple ...
1
vote
0answers
162 views

Set Theory , Konig's Lemma and Infinite Graph Theory

I am trying to understand the basics of Infinite Graph theory and various preconditions in Konig's Lemma. The texts I have studied tend to use the Axiom of Choice (usually Zorn's Lemma) as a tool of ...
1
vote
0answers
49 views

How do I apply vertex or edge coloring to my DAG problem?

I am working on solving a DAG (Directed Acyclic Graph) problem and the part I care about is edge direction and how many ways I can assign directions (while staying acyclic) without making a ...
1
vote
0answers
68 views

Proof of existing path on Depth-First-Search spanning tree

Let $G$ be an undirected connected graph, and $T$ the directed spanning tree of $G$, which I got by performing a DFS on $G$. If $H$ is a complete subgraph of $G$, how can I proof that there a path in ...
1
vote
0answers
46 views

How we show primitive action shows alternating group

I have a graph (as shown in figure), which represents a quotient of the group $$G=\langle A,B,C,D; A^3=B^2=C^3=D^2=(AC)^2=(AD)^2=(BC)^2=(BD)^2=1 \rangle.$$ I proved that $G$ acts 2-transitively and so ...
1
vote
0answers
31 views

Probability of inter-group links in a network with maximum degree 1

In an undirected network, there are two groups of nodes. Group 1 has N1 nodes, and group 2 has N2 nodes. The links in the network are generated following such rules: (1) The maximum degree is 1, ...
1
vote
0answers
388 views

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time.

So we have a graph $G$ with its edges colored by red and blue. we are asked to find a deterministic linear time algorithm that given a parameter $K$ finds a spanning tree of G using exactly $K$ red ...
1
vote
0answers
82 views

References for Hyperbolic Graph Theory

I'm sorry to disturb you but I really got stuck! I can't find any clear and, somewhat, complete reference for this topic. I'm looking for a book, or review, or survey or course notes regarding ...
1
vote
0answers
68 views

Matchings in $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors

Let $G=(V,E)$ be an undirected graph, and let $S,T\subseteq V$ be two sets of vertices with no common neighbors (there can be edges between $S$ and $T$). We need to show that if there exists a ...
1
vote
0answers
48 views

pierre simon laplace and his knowledge of the (Laplacian) matrices

so as we all know, there is a graph matrix called the Laplacian that is used in some eigenvalue/eigenvector/graph theory/spectral theory problems. i'm wondering if the name of this matrix is ...
1
vote
0answers
37 views

How to show that the spectral radius of a binary tree approaches exp(1) as the N tends to infinity?

How can I prove mathematically that the spectral radius of a binary tree approaches e as the number of nodes tends to infinity? I mean it is true that the increase in nodes number is exponential but ...
1
vote
0answers
42 views

Determine the number of simple 7-vertex, 4-regular graph that are pairwise non isomorphic.

I'm taking an introductory graph theory course and I am having trouble going about answering this question. I've been told to look at the graph compliment but I don't quite understand how that ties ...
1
vote
0answers
85 views

zarankiewicz problem lower bound

I was just reading through the following article: http://page.mi.fu-berlin.de/szabo/PDF/stoc96.pdf On page 2 they give an explicit formula for the lower bound of the size of the graph. Summary: We ...
1
vote
0answers
251 views

solutions to flow free game

In flow free, the goal is to connect dots with the same color using pipes, and pipes may not cross. (https://play.google.com/store/apps/details?id=com.bigduckgames.flow) Every square in the grid has ...
1
vote
0answers
272 views

Rigorously prove that a u-v walk implies a u-v path of equal or lesser length .

I am trying to prove the following as an unofficial exercise for a course I'm in: Walks and paths in a graph Prove: For any graph if there is a k-length walk between two nodes, then there exists a ...
1
vote
0answers
28 views

how to prove that every complex circuit is a union of simple circuits

I have an euler circuit in a graph, and I want to prove that in-degree=out-degree. I know that if I can split the original circuit to simple ones, then every simple circuit has in-degree=out-degree. ...
1
vote
0answers
30 views

Can't figure out how to prove Eulerian circuit

I have a graph that is undirected, connected and every vertex has an even degree and I want to prove that a graph like that has a circuit that goes through all edges and only once. I searched the ...
1
vote
0answers
126 views

Upper and lower bound for travelling salesman path.

Let $G$ be a complete graph with weights. $MST(G)$ is the length of it's minimal spanning tree and $TSP(G)$ is the length of minimal travelling salesman path (length I suppose it's the sum of weights ...
1
vote
0answers
38 views

Number of touching triplets in hypersphere packing contact graph

I would like to know what is curently known about the number $N$ of touching-triplets involving a given vertex $V$ in the contact-graph of $d$-hypersphere packings. For $d=2$ and $d=3$, one has $N = ...
1
vote
0answers
48 views

Biconnected graph

Let $P$ be a piece of a bi-connected graph with respect to a cycle $C$. Show that if $P$ has at least one vertex, the number of edges of $P$ is greater than or equal to the number of attachments of ...
1
vote
0answers
72 views

minimum strength of the edges occurring in any path P

Let $G=(V,E)$ be a graph and let $s: E \to \mathbb{R}^+$ be a function. Let us call $s(e)$ the strength of the edge $e$. For any path $P$ in $G$, the reliability of $P$ is, by definition, the minimum ...
1
vote
0answers
57 views

Showing that two given graphs are homeomorphic

I won't to verify whether the two graphs given above are homeomorphic. I am not sure of the method to verify this. I would much appreciate if anyone could give some assistance. Thanks
1
vote
0answers
241 views

Area optimization: Packing rectangles inside rectangle

Background: I am scrambling to figure out the optimization algorithm to build sprite image, which is essentially a big container rectangular image, with multiple rectangular images. I have found an ...
1
vote
0answers
55 views

Finding the diameter of a graph with a complex structure

I know the diameter of the above graph is 6. But I don't know a formal way of doing this. However I know it is possible to draw a matrix considering the minimum distance between the vertices but ...
1
vote
0answers
161 views

what are the advantages and disadvantages of Belief propagation

Belief Propagation cannot solve the graphical model which has cycles. For undirected graphical model for example MRF and CRF in computer vision area, in which cases the model has no cycle ? As far as ...
1
vote
0answers
37 views

Necessary and sufficient condition for an Euler circuit

I have come across the theorem A connected multigraph with at least two vertices has an Euler circuit if and only if each of its vertices has even degree. I just want to know whether the same holds ...
1
vote
0answers
96 views

Can you identify this graph

Could someone identify this graph for me? I apologise for the lack of technical vocabulary, I hope I can describe this clearly enough nonetheless. The graph is formed by the vertices and edges of a ...
1
vote
0answers
85 views

Expansion of subsets of a hamming ball in hypercube

Consider a hypercube graph $G_n = (V,E)$ in n dimensions. Let $H_{1/2} \subset V$ be the set which represents the hamming ball of radius $n/2$. That is for every $v \in H_{1/2}$ the hamming weight of ...
1
vote
0answers
64 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
64 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
93 views

Proof of the Surfer Model Pagerank formula

How do you prove this formula for the Surfer Pagerank algorithm mathematically? ...
1
vote
0answers
39 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
78 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
81 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
55 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
18 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
221 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
43 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
48 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
30 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
149 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 ...