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
0answers
13 views

Matrix norm to compare two graphs

I have the adjacency matrices of two undirected graphs. I want to measure how different the two matrices are in terms of the linkage. Both matrices have the same number of nodes, but they differ in ...
0
votes
0answers
11 views

Find a kernel in a directed graph.

It's a question from a sample exam I'm trying to solve but with no success yet. Let $G(V, E)$ be a directed graph. set $A \subseteq V$ is a kernel if: i. $\forall u,v\in A \implies (u, v), ...
0
votes
1answer
21 views

Finding all mapping between two isomorphic graphs

Is there any formula for counting all the mappings between two isomorphic graphs? I have the following two graphs. and I am trying to find the mappings in the following way. For each edge in ...
1
vote
1answer
13 views

Eccentricity of vertices in a graph when eccentricity of one vertex is given

I have a very basic doubt. If a vertex in any graph has the eccentricity two, then what can be concluded about eccentricities of other vertices in graph. Is the eccentricity of every vertex is less ...
0
votes
1answer
26 views

Removing cycle from the complete graph.

How can I remove $6-length$ cycle from the $K_6$ complete graph so that it'll result a $K_{3,3}$ bipartite graph? I've tried a couple of ways, but I can't get needed result. Maybe this decomposition ...
-1
votes
0answers
22 views

Is the following graph chordal?

A very simple question: Is the following graph a chordal graph? \usepackage{amsmath, amssymb} \usepackage{amsthm} \usepackage{geometry} \usepackage{color} \usepackage{graphicx} \usepackage{calc} ...
-1
votes
0answers
42 views

Count suggestions to be send

A site currently has N registered users. As in any social network two users can be friends. We wants the world to be as connected as possible, so we want to suggest friendship to some pairs of users. ...
-1
votes
1answer
38 views

Friends meeting at point

N friends live in different houses spread across the city.There are M roads connecting the houses. The road network formed is connected and does not contain self loops and multiple roads between same ...
17
votes
2answers
222 views

Is this graph connected

Define the following equivalence relation $\sim$: We have $a \ \mathcal{R} \ b$ if and only if $a+b \ | \ ab-1$. $a \sim b$ if and only if there exist a sequence of integers $a_1, \ldots, a_n$ such ...
1
vote
2answers
59 views

Proof of an $\iff$ statement on binary trees

Let $x$ and $y$ be two nodes of a binary tree $B$. Prove that $x$ is an ancestor of $y$ $\iff$ $x$ stands before $y$ in the pre-order traversal of $B$ and $x$ stands after $y$ in the ...
0
votes
2answers
91 views

Planar graphs where every face boundary is a cycle of even length are bipartite

Let $G$ be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that $G$ is bipartite. If every face boundary is a cycle of even length, ...
0
votes
1answer
79 views

3-regular connected planar graph

Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one face of degree 4. Determine the number of ...
1
vote
3answers
24 views

Find an odd-length cycle in an undirected graph.

I have an exam next week and I found a question that I have difficults to solve: Given the following: Input: Simple undirected graph $G(V, E)$. Output: Find an odd-length cycle in $G$ or ...
-3
votes
0answers
42 views

Party-dance-boys-girls [on hold]

At a party,there are $n$ boys and $n$ girls.Each boy danced with exactly $k$ girls and each two boys danced with exactly $d<k$ common girls.Show that each girl danced with exactly $k$ boys and each ...
0
votes
1answer
22 views

Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that $H$ contains at least $m-n+1$ cycles.

Can someone please verify the proof I just wrote, or offer suggestions for improvement? Also, how do I prove the base case? Let $H$ be a simple graph on $n$ vertices that has $m$ edges. Prove that ...
0
votes
1answer
20 views

If $G$ is connected then $\lambda_2 < \lambda_1$.

Let $G=(V,E)$ be an $n$-vertex , undirected graph with maximum degree $d$, then how to prove the following result. If $G$ is connected then $\lambda_2 < \lambda_1$. where $\lambda_1 \geq \lambda_2 ...
0
votes
0answers
39 views

Face Boundary and bipartite question classification

Is this question wrong? Let G be a connected planar graph with a planar embedding where every face boundary is a cycle of even length. Prove that G is bipartite. Consider a graph of 2 squares ...
1
vote
3answers
34 views

Graph Realization Problem

Given degrees of nodes, is it possible to construct a graph with those degrees, and if yes devise the algorithm? I know of Handshaking Lemma that describes my problem, and another algorithm for it as ...
1
vote
1answer
27 views

Tutorial on Complex Networks

Can anyone advise mea nice and short tutorial about Complex Networks? I'm reading "Networks: An Introduction" from Mark Newman, and is a bit tedious... Thanks PS: There isn't a tag "complex networks" ...
2
votes
1answer
41 views

Partition of graph with maximal score

Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within ...
0
votes
1answer
55 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
49 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
37 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
28 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$. ...
0
votes
0answers
72 views
+200

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 & ...
6
votes
1answer
77 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
0answers
20 views

What is the edge called that converts a tree to a directed acyclic graph?

Neither Wikipedia nor mathworld gave the answer: What is the name of the edge (or multiple edges) without which a DAG would be a tree? Or maybe instead: What is the name of the subgraph such that ...
0
votes
1answer
20 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 ...
3
votes
0answers
34 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 ...
0
votes
0answers
32 views

Min. Spanning Tree - Same weight

Prove that every minimum spanning tree of a connected graph, $G$, has the same maximum edge. Intuitively, this makes sense to me. You need to have that heavy edge because that is the cheapest ...
2
votes
1answer
21 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
36 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
23 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
40 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
38 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
38 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
34 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 ...
2
votes
1answer
49 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)?
3
votes
0answers
65 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
19 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
25 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 ...
2
votes
1answer
38 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
37 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
22 views

Generators Trees in a Tree

My question is very short: How many spanning trees have a tree? Thanks in advance
1
vote
1answer
32 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 ...
0
votes
0answers
14 views

Hypergraph notation and hypergraph morphisms

There are two parts to my question. The first part is about notation for hypergraphs. The sconed is about the notion of morphisms for hypergraphs. For the notation part, the context is that I make ...
6
votes
1answer
45 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
15 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
51 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
24 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