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

0
votes
1answer
10 views

Dimension of the cycle/bond space in graph theory

I'm going through the book 'Graph theory', written by Bondy and Murty. I'm currently trying to grasp the idea of bonds, but I find this a rather difficult concept. So my first question is if someone ...
1
vote
0answers
14 views

Shortest route with a requirements set

Suppose you have a weighted connected graph, $G(V, E)$, with $n$ nodes such that every node has a edge to every other node (a large clique). You are also given a set of sets, $\{l_1, l_2, ... l_n\}$ ...
-1
votes
0answers
6 views

Acyclic edge coloring of a k-regular graph [on hold]

I need to prove this: Acyclic edge coloring of a k-regular graph uses at least k+1 colors (k>=2), why? Help please
0
votes
1answer
10 views

How would I find a minimum weight spanning tree for W?

If I were to let $W$ be the weighted graph formed by taking a complete graph $K_5$ on five vertices 1, 2, 3, 4, 5 with the weight of each edge $\{x,y\}$ given by $(\{x,y\}) = x + y$, how would I find ...
1
vote
0answers
28 views

Convex planar graphs

A planar graph is called convex, if it can be drawn in a way such that every face, including the outer face is convex. Wikipedia states that a planar graph is convex if and only if it is a ...
0
votes
0answers
9 views

The Whitehouse simplicial complexes and compositional (Lagrange) inversion

Associahedra and Lagrange inversion of ordinary generating functions (OEIS A133437): For an o.g.f $ f(x)= a_1x+a_2x^2 + \cdots$ with inverse $f^{(-1)}(x)= b_1x+b_2x^2 + \cdots$, the compositional ...
2
votes
1answer
15 views

Round table arrrangement for 13 people using graph theory

13 Members of a new club ,meet each day for lunch at a round table. They decide to sit such that every memher has different neighbours at each lunch.How many days can this arrangement last? ...
0
votes
1answer
15 views

Prove that there is an orientation of $G$ in which no directed path has length $2$ if and only if $g$ is bipartite.

Let $G$ be a graph of order $n\geq3$. Prove that there is an orientation of $G$ in which no directed path has length $2$ if and only if $G$ is bipartite. I don't know if I understand this correctly, ...
0
votes
1answer
19 views

number of vertices a special graph

Suppose a tree G has exactly one vertex of degree i for each 2<=i<=m and all other vertices have degree 1. How many vertices does G have?
1
vote
0answers
13 views

Example of Normal Tree

A rooted tree $T\subseteq G$ is normal in $G$, if end vertices of every $T$-path in $G$ are comparable in tree order of $T$. This definition is somewhat odd. I am looking an example of graph $G$ with ...
1
vote
1answer
24 views

For every vertex of a Graph G, k(G-v) = k(G) or k(G-v) = k(g) -1?

can you help me with my homework ? "Prove or desprove : Let $G $ be a nontrivial Graph. For every vertex of a Graph $G$, $k(G-v) = k(G)$ or $k(G-v) = k(g) -1$ " I think the answer is : "Once we ...
2
votes
0answers
37 views

Is there a graph with these properties?

Is there a simple undirected graph with the following properties ? Each vertex has at least degree $4$ Each vertex is start vertex of some hamiltonian path The graph does not contain a hamilton ...
0
votes
0answers
13 views

Pina's algorithm

I have difficulty to understand the Pina's algorithm for enumerating all cycle bases of the undirected graphs. -Could you please explain to me using a detailed example ?
1
vote
1answer
37 views

Cycles and faces in planar graphs

Let G be a connected planar graph. Supopose, we know all cycles of G. Is this enough to determine the length of the face boundaries ? In particular, are the lengths of the face boundaries unique ...
0
votes
1answer
29 views

Prove that if $D$ is a digraph such that $od(v) \geq k \geq 1$ for every $v \in V(D)$ then $D$ contain a cycle of length at least $k+1$

Prove that if $D$ is a digraph such that $od(v) \geq k \geq 1$ for every $v \in V(D)$ then $D$ contain a cycle of length at least $k+1$ I tried to prove this by induction. So here is what I got so ...
0
votes
1answer
13 views

Prove that there exist regular tournament of every odd order but there is no regular tournament of even order.

Prove that there exist regular tournament of every odd order but there is no regular tournament of even order. Here is what I got so far. Let $T$ be our regular tournament of order $n$. Since $T$ is ...
0
votes
2answers
18 views

Direct graph proof.

Prove or disprove: There exists a non trivial graph $D$ in which no two vertices of $D$ have the same out degree but every two vertices of $D$ have the same in degree. I don't think this statement ...
4
votes
1answer
57 views
+500

How many directed graphs of size n are there where each vertex is the tail of exactly one edge?

In a research problem in an unrelated area, me and a student found it necessary to count the number of directed graphs with every vertex having one outward-pointing edge, with no restrictions on the ...
4
votes
1answer
55 views

Finding a general equation for number of paths through grid

I started with a 4x4 grid (although I want to eventually generalize for an n x n grid). You must move through a grid on the squares, not on the grid lines. The number of paths for path length = 1 is ...
0
votes
1answer
26 views

Connectivity in Graph Theory if we add a new vertex in a k-connected graph

I am having trouble with my homework in graph theory. Someone can help me? Let v1,v2 ,...,vk be k distinct vertices of a K-connected graph G. Let H be the graph formed from G by adding a new vertex ...
-1
votes
1answer
28 views

Question about trees, Let T be a tree with n vertices

Are my answers correct to these 3 questions? Let T be a tree with n vertices. 1) What is the average degree/valency of the vertices in T? Average Degree of of ...
0
votes
1answer
22 views

For a Cycle Graph is there only one Spanning tree?

For example a Cycle Graph C200 has only 1 spanning tree right? Because adding just one edge to a spanning tree will create a cycle?
0
votes
1answer
22 views

Proving a subgraph is regular

Given positive integer k, let H be the subgraph of Q_{2k+1} (a 2k+1 cube) induced by the vertices in which the number of ones and zeros differs by 1. Prove that H is regular and compute the order and ...
3
votes
0answers
50 views

A cycle of size at least $\frac{n}k$ in a graph with at least $3k$ vertices

My question is this: In a $G=(V,E)$ where $\alpha(G)\leq k$ (the maximum of the size of an independent subset of $G$) and $|V|=n\geq3k$, show that there is a cycle of size $\geq \frac{n}k$. Now, ...
2
votes
0answers
34 views

Algorithm to lay out orthogonal connector lines without overlap

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
0
votes
1answer
17 views

First order logic formula for complete graph with no self loops

I wanted to translate a party scenario where everyone shakes hands with everyone else into a first order logic statement. Since no one can shake hands with themselves, there can be no self loops. I ...
0
votes
1answer
16 views

Chromatic Number and Average degree

Is there any relation between average degree of a graph and chromatic number? Like if an average degree for a graph is 3.4. Can we say that the graph is not 2-colorable? for Number of edges = 17 and ...
0
votes
1answer
39 views

Edge choosability(edge list coloring) of bipartite graphs

It was proved by Galvin that the list chromatic index of bipartite multigraph $G$ equals to it's (ordinary) chromatic index: $$\chi_l'(G) = \chi'(G)$$ Let's use definition of choosability below: ...
1
vote
1answer
23 views

Possible eigenvalue of Laplacian

I came across an exercise of book Spectra of Graphs. Show that there does not exist graph whose adjacency matrix eigenvalue is -1/2. Any thougts?
2
votes
0answers
46 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
1
vote
1answer
20 views

Star-Comb Lemma

I cannot understand that how can we apply Zorn's lemma here. What is the order set?
1
vote
0answers
16 views

Total number of possible graphs in a network with $m$ edges and $n$ vertices?

How do you calculate the total number of possible graphs in a network with $m$ undirected edges and $n$ vertices? No self-loops. For instance, if I have a network with $7$ vertices in it, I want to ...
-1
votes
0answers
31 views

complete graphs and their properties.

Let $$G = K_{20}.$$ The number of edges in a complete graph is $$\frac{(n-1)n}2.$$ So for $n=20$ this is $(20)(19)/2 = 190.$ My question asks to calculate the minimum number of edges to be deleted ...
0
votes
1answer
29 views

How many spanning trees does the cycle graph C2014 have?

How many spanning trees does the cycle graph $C_{2014}$ have? How do I create a bipartite graph and use it to solve this problem?
0
votes
2answers
30 views

Minimum vertices set bipartite graph covering

I was wondering if anyone here could give me any pointers as to how to solve the following problem. Let B=(L,R,E) be an undirected bipartite graph, ∀u∈L, ∃ s= {ei(u,wi)} ∈E; i=1,2.....n connect u to ...
5
votes
0answers
62 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
0
votes
0answers
20 views

How many different graphs are there with a given degree-sequence?

Let G be a simple undirected graph. If it has at most $4$ edges, there is only one graph for any degree-sequence, but for $n = 5$, the situation changes. There are $34$ different (non-isomorphic) ...
6
votes
1answer
63 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
1
vote
0answers
17 views

Meeting with R participants

A meeting has R participants. All participants arrive and leave at different times, but it is always true that within any 3 of them there is always at least 1, who has met the other 2. Prove that then ...
0
votes
0answers
18 views

Let G be a graph and M and N be maximum matchings in G. Characterize the subgraph G|_{M+N}

I have come across this problem from my graph theory study guide and I have no clue where to begin. This whole section is very confusing. Please help.
1
vote
1answer
35 views

Chromatic Triangles on a k17 graph

If the edges of the complete graph K17 (on 17 vertices with no three collinear) are each colored one of three colours can it be proven to have two or more monochromatic triangles?
6
votes
1answer
80 views

Graph with largest eigenvalue “almost” $\pi$

While doodling recently I found that the largest eigenvalue of the adjacency matrix of the following undirected graph (ignore directions on edges in picture) is "almost" $\pi$. According to octave ...
0
votes
1answer
32 views

Show that there is a path in $G$ contain three vertices whose degree are distinct

Show that if $G$ is a connected graph such that the degree of every vertex is one of 3 distinct number and each of these three number is degree of at least one vertex of $G$, then there is a path in ...
1
vote
1answer
40 views

“Job-scheduling” problem that minimizes the number of machines

In a graph, there are points that need to be visited. For each of these points, there is a certain time interval given by its start and ...
2
votes
0answers
40 views

Cubic 3-edge connected graph has edge cover that can omit 2/3 of all edges over 5 graphs (so 2/15 per graph) and be 2-edge connected

Let's assume that I have a cubic 3-edge connected simple graph $G$. After taking a perfect matching (and we can specify which one we want), I want to split the remaining edges in 5 sets $U_1, ..., ...
0
votes
0answers
10 views

Making a graph with information

I would like to ask what appropriate graph I should use and maybe an example to help me, I am struggling on what type of graph will be appropriate for this, and knowing could help me with the further ...
0
votes
1answer
13 views

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$

Let $G$ be a disconnected graph of order $n \geq 6$ having three components. Prove that $\Delta(\overline G) \geq \frac{2n}{3}$ This is what I got let $u \in V(G)$, since $G$ have three components, ...
0
votes
1answer
22 views

Prove that if $deg(u)+deg(v) \geq n-1$ for every two non adjacent vertices $u$ and $v$ of $G$ then $G$ is connected and $diam(G) \leq 2$

Let $G$ be a graph of order $n$. Prove that if $deg(u)+deg(v) \geq n-1$ for every two non adjacent vertices $u$ and $v$ of $G$ then $G$ is connected and $diam(G) \leq 2$ This is what I got so far ...
1
vote
1answer
35 views

Graph theory: tree vertices

How can I calculate the number of vertices of a tree knowing he has 33 vertices of degree 1, 25 vertices of degree 2, 15 vertices of degree 3 and all other vertices of grade 4?
0
votes
1answer
27 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...