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
1answer
20 views

Ford-Fulkerson for irrational capacities

We know that the Ford-Fulkerson algorithm works for integer capactities but it may loop forever for irrational ones. Is there an algorithm that only alters Ford-Fulkerson slightly but works for ...
0
votes
0answers
8 views

Gallai's implication's for bipartite graphs

I have this exam question: What are the implications (or what is an alternative form) of Gallai's theorem for bipartite graphs. I have been thinking for some time but couldn't come up with anything, ...
0
votes
0answers
38 views

Encoding a graph coloring problem in SAT/CNF for DPLL algorithm

I'm having trouble trying to convert the following problem to SAT for later application to DPLL: Given a connected, undirected graph G, with k colors $\{ c_1 , ..., c_k \} $ and any number of ...
0
votes
0answers
16 views

give an example of r-regular graph that $k(G)\neq k'(G)$

where $k(G)$ is the number of minimum set of vertices in $G$ whose deletion from a graph $G$ disconnects it. and $k'(G)$ is the number of minimun set of edges in G whose deletion from a graph $G$ ...
0
votes
0answers
23 views

Number of graphs which have $m$ connected components in all subgraphs obtained from the complete labeled graph $K_n$ by removing zero or more edges.

Let $Ans_m$ be the number of graphs which have $m$ connected components in all subgraphs obtained from the complete labeled graph $K_n$ by removing zero or more edges. Then we get $\sum_{m}Ans_m$ in ...
0
votes
0answers
12 views

Gilmore-Hoffman characterisation of comparability graphs

Gilmore and Hoffman's characterisation of comparability graphs says that: "$G$ is a comparability graph precisely if whenever $v_1v_2...v_r$ forms a cycle in $G$, such that no $v_i$ and $v_{i+2}$ ...
0
votes
1answer
25 views

Proof of Baranyai's theorem

Could you give me a full proof of Baranyai's theorem. I looked at a lot of sites but they seem to only give partial proofs. I read that Schrivjer proved it using the max-flow-min-cut theorem but I can'...
1
vote
1answer
70 views

Complete Graph with odd degree

It is known that the Complete Graph $K_n$ has $n^{n-2}$ spanning trees. The $K_{10}$ has $10^8$ spanning Trees. Now my question: How can I compute the number of spanning Trees with odd degree of its ...
0
votes
0answers
21 views

Menger's theorem and the max-flow min-cut theorem

I read this question Proof for Menger's Theorem but it's still not clear to me how one proves Menger's theorem using the max-flow min-cut theorem. Could you explain?
0
votes
0answers
43 views

Edge-matching icosahedron puzzle

Color the edges of an icosahedron with 4 colors so that all 20 triangles have a distinct set of colors. Color the edges of an icosahedron with 6 colors so that all 20 triangles have a distinct set ...
0
votes
1answer
6 views

Average Loop Length For N Singly Connected Nodes

Given N nodes where each node links to a single node randomly (links to self are ok, each node has 1 and only 1 node linking to it) what is the average loop length? Example: If you have 100 nodes the ...
0
votes
1answer
13 views

Gallai's theorem on independent edges

In a simple graph of $n$ vertices let $\alpha(G)$: the maximal number of independent vertices (no two of them have a common edge) vertices $\beta(G)$: the minimal number of covering vertices (edges ...
1
vote
1answer
27 views

What is a polynomial with infinite number of terms?

My instructor commented that a structure function $\phi(G)$ of a graph is a polynomial if a finite number of terms. So what is the thing with infinite number of terms? Why not polynomial?
1
vote
1answer
41 views

Graph theory: The average degree of G is at least k

Let $G=(V,E)$ be a simple graph with at least $k+1$ vertices, Suppose that for every two vertices that are not adjacent $u,v$ : $d(u)+d(v) \ge 2k$. Prove or disprove: The average degree of G is at ...
0
votes
0answers
47 views

cycle containing distinct edges

Let $G$ be a $3$-connected graph with three distinct edges $e_1,e_2,e_3$. How can it be proved that a cycle containing all three edges exists in $G$ if and only if: (1) they aren't all incident ...
0
votes
0answers
23 views

Order nodes in a graph to minimize edge crossing

Given an undirected graph, is there any efficient algorithm to order the nodes into a sequence $\langle v_1, v_2, \ldots, v_n \rangle$ s.t. the number of edge crossings is minimized? Two edges $(v_i, ...
1
vote
2answers
27 views

Prove a cube graph has no even walks?

The following question was in my exam, and I didn't even have any idea on how to start, so I'm quite curious to see a proof. I was given a cube graph (the one on the left): The question was as ...
0
votes
1answer
17 views

finding proper coefficient for the two graphs to intersect at one point only

We have two functions such as $y=\ln(x)$ and $y=cx^{1/2}$ and I look for the proper positive coefficient $c$ which satisfies that the graphs of the functions above intersects at only one point. If we ...
6
votes
3answers
150 views

Is there a monoid structure on the set of paths of a graph?

Given a graph G, and the set of paths in G called PathG. Is there a monoid structure on PathG? Will concatenation be the multiplication formula? even if it's not defined for some paths? What about ...
4
votes
1answer
57 views

$A^A$ in category of graphs

(reference is Lawvere/Schanuel, Session 31, Ex. 1) I'm trying to calculate the exponential object $A^A$ and its evalution map $e \colon A \times A^A \to A$ in the category of graphs, where $A$ is the ...
0
votes
0answers
27 views

Given a weighted graph, how to find a node sequence that closed nodes have strong connection.

This may be a graph theory question: Given a weighted undirected graph, large weight means the correlation of the two nodes is big. How can I generate a node sequence such that nodes nearby have ...
3
votes
1answer
64 views

How many sets correspond to connected graphs

I'm trying to solve this project euler problem. I don't want to get too much help, since that would defeat the purpose, but I'm hitting a wall, so I'm asking a related problem here, from which I'll ...
0
votes
2answers
28 views

Planarity found in inducing $K_5$ [duplicate]

I was interested in studying whether or not if when we remove an arbitrary two edges from $K_5$, we get a planar graph. I understand that a planar graph has at most $3v-6$ edges, where $v$ is the ...
0
votes
1answer
74 views

Is there a proof that any graph is “drawable” on a 2D surface? [closed]

Are there any theorems that say something formal about the fact that any graph is drawable on a 2D surface, and can be mapped to a 2D array of pixels if the pixels are infinitely small? EDIT: No ...
1
vote
0answers
51 views

What are some applications of vertex separators?

What are applications of finding a vertex separator that minimizes a cut in a graph. To clarify the problem I am talking about is is given a graph of n vertices and a partition $m_1,m_2,..,m_k $of ...
0
votes
1answer
15 views

Maximum (edge)weight connected subgraph of an undirected graph.

Let G be a undirected graph with weighted edges. I want to find a connected subgraph which has at most L nodes(vertices) whose sum of edges is maximum. It sounds similar to MWCS or PCST but here only ...
-3
votes
1answer
32 views

Find a DFS,BFS spanning tree.

Is my answer right? I think I understood the definition of BFS and DFS spanning tree, but I'm not sure my answer is right. If it is wrong, please correct it.
0
votes
0answers
12 views

Creating Barabási–Albert(BA) graph with spacific node and edgs

I am trying to construct a BA graph with 500 nodes and about 37000 edges. The number of edges to attach from a new node to existing nodes should be at least 91 to make enough number of edges. I ...
0
votes
1answer
30 views

Which vertex-transitive planar graphs represent non-self-intersecting polyhedra?

Consider an infinite planar graph with the following properties. Its vertices all have valence $3$. The faces all have $5$ edges. Now put it in cartesian space and require that the faces are all ...
-2
votes
0answers
17 views

Existence Theorem of Natural Recursion & Mutual Recursion

$f: A -> R$ $f(a)=$ $1. basecase$ $2. g(...h(first loa) f(rest loa))$ Exist a function $F: N-> R$ Q: Is there any theorem that says the existence of this relation? More complicated version ...
1
vote
1answer
26 views

Topological sort into a limited number of bins, each with limited capacity

I'm working on a scheduling/design tool for educational courses. I have lists of courses, some which require others to be taken first (dependencies), others that require courses to be taken together ...
0
votes
2answers
43 views

Permutation of keys inserted into a tree?

Give the fraction of permutations of the keys $A $ through $G$ that will, when inserted into an initially empty tree, produce the same Binary search tree as does $A$ $E$ $F$ $G$ $B$ $D$ $C$ ANSWER: (...
-1
votes
0answers
14 views

Weight of edge in opposite direction of directed graph?

If $w(p_{xy}) = 5$ then what is $w(p_{yx})$? Is it 5 or -5? $p_{xy}$ is the path of the xy edge, obviously. w() is the weight function.
0
votes
1answer
17 views

How can I count the number of faces in $K_2$?

I studied that in $K_2$ we have $V=2$, $E=1$, and $F=1$, and in $K_3$, we have $V=3$, $E=3$, and $F=2.$ But where is the face in $K_2$? There is only one line in there.
4
votes
2answers
43 views

Prove that a sequence of degrees can be the degrees of a simple graph

Hi there I need to show that the sequence $s(n) = \{1,1,2,2,3,3,4,4,...,n,n\}$ can be the degrees of the vertices of a simple graph, $\forall n\geq 1$. So far I have tryied to prove this by induction ...
0
votes
0answers
10 views

Graph properties of Bruhat order for the general linear Lie algebra $\mathfrak{gl}$ on $\mathbb{Z}^n$

Let $P = \oplus_{i\in \mathbb{Z}}\mathbb{Z}\epsilon_i$ the free abelian group of infinite rank. Then we have a natural partial order $\leq'$ on $P$, that is, $a \leq' b $ if and only if $b \in a+\sum_{...
1
vote
1answer
24 views

Help understanding the chromatic numbers of the planes upper bound.

I've been studying the Chromtic number of the plane and it shows that a hexagonal tiling of seven colors shows that 7 is an upper bound. I couldn't actually follow the argument that proves this is ...
1
vote
0answers
18 views

What happen if we remove a newly created vertex resulted from an edge contraction of a 3-connected graph?

There is a little doubt along the way when I tried to prove to prove the following: Let $G\cdot e$ denote the contraction of edge $e$ in $G$. If $G$ does not have a Kuratowski subgraph and the ...
0
votes
0answers
8 views

Weighted mean / average where you reward the lowest value - cost - distance

Best I've several weather-station (200), placed across the country (508 municipalities). Now, I would like to prescribe the weather info, e.g. temperature, to each of the municipalities of that ...
0
votes
0answers
23 views

The best known bounds for spectral radius of a graph

There are many bounds for the spectral radius of graphs in terms of no. of vertices, maximum degree, chromatic number etc. I wish to know till date what are the best lower and upper bound for the ...
3
votes
1answer
44 views

Filling an NxN table with N numbers

I have been confronted with the following homework question: Let $M$ be a table of size $N \times N$. A legal filling of $M$ with the numbers $\{1,\dots,N\}$ is one such that each cell of the ...
2
votes
1answer
42 views

Are two graphs isomorphic if there is a bijective distance-preserving map between them?

Suppose that there exist two connected graphs $G$ and $H$ and a one-to-one function $\varphi$ from the vertex set $V(G)$ onto $V(H)$ such that the distance $\operatorname d_G(u, v) = \operatorname d_H(...
2
votes
1answer
41 views

Another question on 2-connected graphs.

These days, I have been trying to solve some questions on $k-$connected graphs. I handed over ones, but still there are ones to do. One of still remaining ones is as follows. I appreciate if someone ...
3
votes
1answer
72 views

Does a 2-connected graph, say $G$ have a vertex, say $v$, such that $G-v$ is still 2-connected?

I have been trying to solve this problem for some days. Then, I put the problem here, and it is here for some days. I appreciate it if someone even give me some hint. Assume that $G$ is a 2-...
0
votes
0answers
31 views

Introductory material on Domination in Graphs?

I have found two books Fundamentals of Domination in Graphs and Total Domination in Graphs, uncertain whether good introductory books on domination in graphs. I am personally interested in domination ...
2
votes
3answers
71 views

Prove that there is always a perfect match

Let Gn be a graph with 2n nodes: a0, a1, ..., an-1, b0, b1, ..., bn-1. Let the edges be formed like this: Node ai connects with bj and bk, where j = 2i mod n and k = (2i + 1) mod n Prove that ...
0
votes
0answers
19 views

Which dominations in graphs determined by st-connectivity?

Fundamentals of Domination in Graphs has 75 variations to domination. I am interested in domination determined by st-connectivity such as st-vertex-cuts. An example st-domination measure is Fussell-...
2
votes
1answer
52 views

Hamiltonian circuit in at least one component

I'm having trouble proving that the problem stated in the title is NP-complete, specifically by reduction from Hamiltonian circuit. Intuitively it's clear - Hamiltonian circuit in one graph is NP-...
1
vote
2answers
32 views

Assumption that graph is connected to prove Ore's Theorem

On Wikipedia, the Ore's Theorem says that if $G$ is a finite simple graph with $n \ge 3$ vertices and for all non-adjacent vertices $u$ and $v$, the sum of their degrees is greater than or equal to $n$...
2
votes
1answer
42 views

Graph-Theory: Find matching in bipartite graph

Let $G=(V,E)$ be a graph such that $V=X\cup A\cup B$ . $X,A,B$ are independent sets and pairwise disjoint. Suppose that $|X|=63,|A|=|B|=9$, the degree of every vertex in $A\cup B$ is 7, and every ...