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

What is a `red vertex` and what is a `blue vertex`?

I showed the following question on an exam: let $G(V, E)$ connected indirected graph with positive weights. any vertex is colored with either blue or red. Claim: if edge $(u, v)$ is the ...
2
votes
1answer
71 views

A basic question on random graph

Consider undirected graphs with $n$ vertices. now consider the set of all possible edges (excluding self-loops). now, select edges from the set with probability $p$ independent of the other edges. so, ...
2
votes
2answers
67 views

Calculating the central point with minimal average distance to other points

I work at an office with colleagues coming from all over the country. Our office is quite centrally located, but some colleagues have to travel quite a lot further than others. I often wondered how I ...
5
votes
0answers
160 views

Name for Number of Ancestors/Descendants of Vertex in Directed Acyclic Graph

Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. ...
2
votes
0answers
154 views

a closed formula to enumerate the self avoiding walks of a graph

Let $G$ be a directed graph with $N$ nodes and weighted adjacency matrix $W $ defined by $$ W_{ij} = \left\{ \begin{array}{cl} w_{ij} & \text{ if } \ i \ \text{ is connected to } j \\ 0 & ...
5
votes
1answer
85 views

The rows continue to be different to each other

In each position of an $n \times n$ matrix there is a number. We know that all the rows of the matrix are different from each other. Show that we can delete a column so that the rows of the matrix ...
0
votes
1answer
83 views

The “sides” of a k-regular bipartite graph are equal?

I was reviewing some lectures notes and noticed that in a proof of a theorem our lecturer stated that the "sides" of a k-regular bipartite graph are equal and that it is trivial to prove it. Anyway ...
5
votes
2answers
91 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
3
votes
1answer
133 views

Definition of compatible vertices

I'm reading the Extremal Graph Theory book by Bollobás, and I'm stuck at the definition of 'compatible vertices'. It's here at the bottom of p.13 It says : "Call two vertices compatible if every ...
0
votes
0answers
43 views

How to reduce a graph via decomposition?

Is there a Java / C# library that can be used to reduce a graph via decomposition? Or could someone point me to a good tutorial where I can learn all these? E.g.
2
votes
0answers
98 views

Graph planarity and electronic circuit boards

In another MSE question, I found the following definition for 2-layer circuit board decomposition of a graph: A circuit board is defined as a pair of planar graphs with vertices identified, i.e. ...
0
votes
2answers
85 views

Tree with $k$ edges is a subgraph of any graph with all vertices of degree $\geq k$.

Let $T$ be a tree with $k$ edges. Let $G$ be a graph where every vertex has a degree of at least $k$. Show that $T$ is a subgraph $G$. I know this implies that in a graph where every vertex is at ...
1
vote
1answer
49 views

Interactions between geometry and graph theory.

I'm looking for some nice theories or just exercises, with both geometrical aspects and graph theoretics aspects. Example may include for instance the 4-color theorem or Euler characteristics, maybe ...
1
vote
1answer
85 views

Examples of Matroids

Preparing an exam, I'm looking for examples of matroids and maybe hints or references on proves that they are. (what I already know are representable matroids and graphic matroids)
4
votes
1answer
66 views

Chromatic number of generalized hypercube

It's clear that the chromatic number of $Q_n$ is $2$. But what about the graph $G$ with vertex set ${n}^{(r)}$ where two vertices are adjacent if and only if their coordiantes differ by one? Can't ...
3
votes
1answer
114 views

How to call a tree with a single branch?

How do you call a tree with only one branch (in other words, where every vertex has maximum one direct successor)?
4
votes
0answers
135 views

Minimal number of edges removed to make a graph triangle free

I'm interested in finding an upper bound on the expected value of the minimal number of edges one needs to remove from a random graph $G_{n,p}$ (where each edge appears with probability $p$) in order ...
1
vote
1answer
38 views

Relation between a complete k-partite graph and a perfect graph

Is a complete $k$-partite graph also a perfect graph? I know that the result holds for bipartite graphs. Can we claim the same for higher order partitions?
1
vote
1answer
65 views

Irreducible matrix equivalent connectedness of matrix graph?

If a matrix is irreducible, based on the following definition A matrix is reducible if there are two disjoint sets of indexes $I,J$ with $|I|=\mu$, $|J|=\nu$, $\mu+\nu=n$ such that for every ...
3
votes
1answer
905 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
0
votes
2answers
69 views

Graph Theory, with algorithms like kruskal and something more

The new government of the archipelago of Sealand has decided to join six islands by bridges to connect them directly. The cost of building a bridge depends on the distance between the islands. This ...
0
votes
1answer
30 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
1
vote
1answer
809 views

Stable Marriage - set of preferences such that every arrangement is stable?

This is a homework problem from the MIT OCW math for CS class, assignment 4, problem 5. Prove or disprove the following claim: for some n ≥ 3 (n boys and n girls, for a total of 2n people), there ...
6
votes
1answer
53 views

Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs?

Following on from this question: Q: Does $K_{15,15}$ decompose into $K_{5,5}-C_{10}$ and $K_{5,5}-(C_6 \cup C_4)$ subgraphs? or equivalently Q: Does there exist a $15 \times 15$ matrix ...
3
votes
1answer
94 views

Let $G$ be a loop-less undirected graph. Prove that the edges of $G$ can be directed so that no directed cycle is formed.

Can someone please verify my proof or offer suggestions for improvement? Let $G$ be a loop-less undirected graph. Prove that the edges of $G$ can be directed so that no directed cycle is formed. ...
1
vote
1answer
60 views

Film Festival, with intersections graphs

I encourage you to read this problem. I have a doubt, have films 1 and 2 the same type? I read the problem and I think that films {1,3,5}, {2,4,6}, {3,4} and {5,6} are grouped, but not is the case ...
1
vote
1answer
32 views

Draw a graphic only passing one time

I would like to know when I can draw a graph, without lifting the pencil and passing once for each edge? What theory is behind that? Thanks for your time
0
votes
1answer
41 views

Homomorphism from a commutative group?

I came across this question in a practice exercise and can't quite understand it. If f is a homomorphism from a commutative group $(S,*)$ to another group $(T,*')$, then prove that $(T,*') is also ...
3
votes
1answer
102 views

A graph on the cities of a country

In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is ...
3
votes
1answer
398 views

Draw this shape - no double lines, no lifting pen? Impossible!?

I'm 99% sure this isn't possible! But... is there anyway to draw this shape without lifing the pen and without redrawing over any lines?! Thanks :-)
0
votes
1answer
61 views

Making a Graph having edges

V is the set of those two-letter words built over {w, x, y, z} whose first letter is y or z. The graph G = (V, A) is defined so that two words of V determine an edge of A if they differ in exactly one ...
2
votes
0answers
71 views

Proof of chromatic number of a graph

Let $G$ be graph, let $x\in V(G)$ with $|\delta_G(x)|=\Delta(G)$. For all other nodes $v\in V(G)\setminus\{x\}$ let $|\delta_G(x)|\lt\Delta(G)$. Furthermore assume we have $v_1,v_2,v_3\in V(G)$ ...
3
votes
0answers
36 views

Connected graph where edge costs depend on a parameter $t$. Find the $t^*$ which gives the minimum cost minimum spanning tree.

The set-up: Let $G=(\,V,\,E\,)$ be a connected graph. Associated with every edge $e\in E$ is a cost/weight function $f_e(t) = a_e t^2 + b_e t + c_e $, where $a_e>0$. For a fixed $t$ we can define ...
1
vote
0answers
137 views

Research Topics Needed

This coming academic year a professor has asked me to find some topics that I wish to pursue to write about. The problem/topic that will be discussed doesn't have to be open, but my trouble is that I ...
5
votes
2answers
99 views

Does $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs?

Q: Does the complete bipartite graph $K_{12,12}$ decompose into $K_{4,4}-I$ subgraphs, where $I$ is a $1$-factor (i.e., a perfect matching)? The obvious necessary conditions work: $K_{12,12}$ ...
0
votes
1answer
31 views

New way of combining information in graphs

So, I am working for a social project involving graph theory. I have a dynamic dataset (weighted and undirected), I made graphs out of them ( for 10 years ). Now, I am trying to find out relations ...
4
votes
1answer
241 views

Textbooks on graph theory

I've read the textbook Groups and Their Graphs by Grossman, and I'm interested in learning more about graphs. I know about O. Ore's book in the same series (Graphs and Their Uses), but I'm interested ...
1
vote
0answers
89 views

Round robin tournament scheduling with additional constraints

I'm looking for a solution to the following problem. Given $n = a\cdot (b-1) + 1$ players, $a$ and $b$ being integers with $a \leq b$, I want to schedule a round-robin tournament where every player ...
5
votes
1answer
101 views

All $k$-regular subgraphs of $K_{n,n}$ have a perfect matching: a proof without Hall's Marriage Theorem?

There are several ways of describing this result: Theorem: For $k \in \{1,2,\ldots,n\}$, any $k$-regular subgraph of $K_{n,n}$ has a perfect matching (also known as a $1$-factor). I tend to ...
1
vote
1answer
70 views

Partition Graph Challenging Question

I want to find in which of the following Graph, the edges cannot partitioned to triangles? Km,n,r means 3-Partite Complete Graph with m, n, and r sections. a) K7 b) K12 c) K3,3,3 d) K5,5,5 i ...
0
votes
1answer
26 views

Planner Combination Problem on Graph

I ran into a Graph Problem. Suppose G is A Planner Graph with 100 Vertices such that if connect each two Non-adjacent vertices, the resulting graph would be non-planner. what is the number of edges ...
1
vote
1answer
90 views

Perfect Matching Combination Problem

We know: A perfect matching (a.k.a. 1-factor) is a matching which matches all vertices of the graph. if we remove edges of perfect matching of a 12-Complete Graph. how many triangle remain in this ...
1
vote
2answers
62 views

graph theory: show that for k=4 hesse diagram is not a planar graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
2answers
57 views

In a 2-connected simple graph, is there always a simple cycle containing any given path P and disjoint edge e?

For any finite simple graph $G$ which is 2-connected, given a path $P$ and a disjoint edge $e$, is it true that there is always a simple cycle containing $P$ and $e$? If instead of an edge $e$, a ...
1
vote
1answer
222 views

Convert adjacency matrix to graph

Is there any online service that can provide possible graphs (the simplest one) when I give a sequence of integers (node degrees) as input (or reject the input) -based on Erdős-Gallai formula? Thanks ...
0
votes
1answer
26 views

graph theory: the degree of vertices in an hesse diagrem graph

In this picture you can see the hesse diagrem of $\subseteq$ over $P(\{x,y,z\})$ For the set $A$ with $k$ elements, $k>0$ look at the diagram as a graph, it's vertices are the members of $P(A)$ ...
0
votes
1answer
241 views

graph vertex chromatic number in a union of 2 sub-graphs

$G_1$ is graph on the set of vertices $\{1,2,3,4,5,6,7,8\}$, $G_1$ vertice chromatic number is 5. $G_2$ is graph on the set of vertices $\{7,8,9,10,11,12,13,14,15,17,18,19,20\}$, $G_2$ vertice ...
0
votes
2answers
38 views

Number of spanning trees of a graph (behind the formula)

Given $G$ a subgraph of $K_n$ s.t. $G$ has $n$ vertices with adjacency matrix $A$; why is $$\sum_{T \text{ spanning tree of }K_n}\prod_{(i,j)\in T}A_{i,j}$$ the number of spanning trees? I can't get ...
1
vote
1answer
597 views

Graph with edge disjoint cycles

If the vertices of graph have a degree of at least $n\geq2$, show that the graph has at least $\frac{n}{2}$ edge disjoint cycles. Unsure how to approach this, but I understand that edge disjoint ...
2
votes
1answer
184 views

Connected bipartite graph

Let $G$ be a bipartite graph with $n$ vertices. Prove that if every vertex has degree at least $\frac{n}{4} + 1$, then $G$ is connected. I'm assuming that number of vertices in this bipartite graph ...