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

3
votes
0answers
126 views

Maximal unit lengths in 3D with $n$ points.

Given $n$ points in 3D space (V), what is the maximal number of unit distance lengths (E) between those points? Here are a few possibilities. Some of them are chromatic spindles. ...
0
votes
1answer
30 views

A graph such that every set $S$ of vertices has at least $\frac32|S|$ neighbors, then $(\frac32)^{\frac{\text{diameter}-4}{2}}\leq n$

Let $G=(V,E)$ be a graph with $n$ vertices and with diameter $k$. Let $N(S)=\cup_{s \in S} N(s)$ denote the set of neighbors of $S \subseteq V$. Suppose that every set $S\subset V$ of size at most $\...
0
votes
0answers
36 views

suppose that $ r_{n} =(3, 3, 3, …, 3)$ ramsey number show $r_{n} \leq n(r_{n-1} - 1) +2$ [duplicate]

$r_{n}$ is ramsey number for $k_{1}, k_{2},..., k_{n}$ which it means the smallest size of a set which if we color all pairwise the element with n color we certainly could find a set of element with $...
0
votes
1answer
37 views

What is the necessary and suffices condition to build an r -regular graph?

I need to show what is necessary and suffices to have an r-regular graph with n vertices. where $n > r+1$ One way is to build that r-regular graph with n vertices ...
-1
votes
2answers
61 views

Is every finite category identifiable with a directed multigraph? (and vice versa?) [duplicate]

What seems implicit in this talk on youtube, is the claim that every directed multigraph (with loops) can be identified with a finite category and vice versa, if we consider the paths of the directed ...
1
vote
3answers
82 views

Is “Connected Component” unique for each graph?

Definition A connected component of an undirected graph $G$ is a subgraph where any two vertices are connected by paths. A connected component is a maximal connected subgraph in $G$. Consider a ...
2
votes
1answer
64 views

Show that for each of the following graphs G there exists up to isomorphism precisely one category A with G(A) = G.

I was working through the exercises in Abstract and Concrete Categories: The Joy of Cats (http://katmat.math.uni-bremen.de/acc/acc.pdf) and I was stuck on exercise 3A.(d). It seems to me that the ...
1
vote
1answer
98 views

Eigenvalues of periodic lattice Laplacian?

Consider the graph given by taking a rectangular lattice with $m$ rows and $n$ columns and joining each vertex to its four nearest neighbors, where vertices on the boundary are connected periodically (...
2
votes
1answer
33 views

Minimal alpha-Spanning Tree

I got a really strange question with a definition that I've never seen before, so I hope someone of you can help me with it: Let $G = (V,E)$ be a connected graph and $\alpha \in \mathbb{R}$. A graph $...
0
votes
0answers
49 views

Strategy of ball math game

Found math game: http://www.emathhelp.net/math-games-and-logic-puzzles/rgbw/ What is a strategy for it? I can make 15 white balls max. Any thoughts?
5
votes
0answers
129 views

Points with power distances

It's possible for seven points to be at integral distances. I'm dallying with powered triangles, though, so I'm looking for point sets where all distances are powers of a fixed $x$ value. For example,...
1
vote
0answers
30 views

Notation for directed and undirected edges of a graph

Let $G$ be a directed graph. I want a way to talk about the edges of $G$ without orientation, so I defined a function $u$ for "unorient" which takes $G=(V,E)$ to $u(G)=(V,E')$ where $$E'=\{\{v,w\} \...
4
votes
2answers
44 views

Hall's marriage thereom with max-flow-min-cut

I heard that Hall's marriage theorem can be proved by the max-flow-min-cut theorem. Could you outline how that is possible? Hall's theorem says that in a bipartite graph there exists a complete ...
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
47 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
13 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
26 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
72 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
49 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
7 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
14 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
29 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
53 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
30 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
155 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
28 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
65 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
52 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
20 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
37 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
18 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
32 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 ...
1
vote
1answer
27 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 ...
1
vote
2answers
44 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: (...
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
44 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
25 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 ...