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

Does it make sense to apply the Manhatten metric to an arbitrary graph?

I overheard someone talking about using the Manhatten metric against nodes on an arbitrary graph (or even a tree). At the time, I didn't think much of it, but having dwelled upon it, does it even make ...
1
vote
0answers
46 views

Graph: I absolutly don't understand what they want to say with this theorem.

I'm stuck since 3 days on this theorem, but I can't interpret it. What the hell do they want to tell us ?
0
votes
0answers
22 views

Size of the connected components

Assume that we have a disconnected graph with a random number of connected components. Is there any bounds/distribution on the size of these connected components (the number of vertices). The degree ...
4
votes
1answer
25 views

Sub graph of a graph up to isomorphism?

Let $G=(V,E)$, where $\{a,b,c,d\}$ and $E=\{ab,ac,ad,cd\}$. Draw all the sub graph of $G$ up to isomorphism. Here is my attempt: Am I right? Are this the only sub graphs of $G$ up to isomorphism? ...
1
vote
1answer
31 views

Combinations for pairing groups

I have a little bit of a complex question and I don't know anything about combinatorics, but I'm working on software problem and I'm trying to figure out how my algorithm will scale. I'm having to ask ...
-7
votes
0answers
45 views

How to prove that one guy in all groups [on hold]

I dont know how even think about it. Anyone? thanks
1
vote
1answer
39 views

Graph Theory and vertices

For each of the graphs described below, state whether or not such a graph exists. For those that do exist, draw an example of such a graph. For those that do not exist, explain why they do not exist. ...
0
votes
2answers
15 views

What is meant by “Each of two concentric discs has 20 radial sections of equal size”

Can someone show me a picture representation of the following question: Each of two concentric discs has 20 radial sections of equal size. For each disc, 10 sections are painted red and 10 blue, in ...
0
votes
0answers
31 views

Describe in words the product of the adjacency matrices for $G^3$ and $G^4$

Let $G$ be a directed graph with 10 vertices. Let $A$ be the adjacency matrix for $G^3$ and $B$ the adjacency matrix for $G^4$. Describe in words what the product $AB$ represents. I know that the ...
1
vote
1answer
22 views

A question on $k$-connected graphs [duplicate]

I'm looking for a proof of this theorem by Dirac: If a graph is $k$-connected for $k \ge 2$, then for every set of $k$ vertices in the graph there is a cycle that passes through all the vertices in ...
1
vote
1answer
24 views

What is the difference between Maximal and Maximum Cliques

Hardly I can not find the clear differences between Maximal and Maximum Cliques, As I think Maximal means a graph can not be extended to connect more edges , means each node is connected with all ...
0
votes
2answers
17 views

what is the counter example to minimality of coloring a graph in BFS manner?

i was thinking of below algorithm i use a queue Q to performs BFS and i use an arbitrary start vertex s. each vertex v has attribute v.color which specifies it's color. ...
3
votes
0answers
15 views

Show that every cubic K4-free graph G has a bipartite subgraph with at least m-n/3 edges

Suppose $G$ is a cubic $K_4$-free Graph with $m$ edges and $n$ vertices, prove that there exists a bipartite subgraph of $G$ with at least $m-\frac{n}{3}$ edges. I can only prove we can find a ...
1
vote
1answer
24 views

How to find that two adjacency matrices are equal

What is the easiest way to tell if these two graphs are isomorphic and how do I know which nodes in both graphs are the same. I've made the adjacency matrices but they are pretty big. I think I need ...
-3
votes
0answers
39 views

Why a graph $G=(V,E)$ has either one vertex $v\in V$ such that $\deg v\geq\sqrt n$ or all vertex has degree less that $\sqrt n$ [on hold]

We suppose $|V(G)|=n$. Why a graph $G=(V,E)$ has either one vertex $v\in V$ such that $\deg v\geq\sqrt n$ or all vertex has degree less that $\sqrt n$ ?
1
vote
1answer
13 views

Prove that if $\delta(V)\geq 2$, the graph $G=(V,E)$ has a cycle of length $\delta(V)+1$.

Let $\delta(G)=\min_{v\in V}d(v)$ where $d(v)$ is the degree of $v$. Prove that if $\delta(G)\geq 2$, the graph $G=(V,E)$ has a cycle of length $\delta(V)+1$. It look to have a problem... take ...
1
vote
0answers
16 views

How do we derive efficiency from robustness in the virtual ant solution to the traveling salesman problem?

Using virtual ants/swarm intelligence to solve the Traveling Salesman Problem is an example of using a robust system to solve an efficiency problem. We normally think of robustness and efficiency as ...
1
vote
1answer
11 views

Is the Turán graph $T_{k,n}$ vertex-transitive when $n$ is a multiple of $k$?

Take $k,n$ to be two positive integers, such that $n$ is a multiple of $k$, say $n= k m$ for some integer $m$. Consider the Turán graph $T_{k,n}$, i.e. the complete $k$-partite graph with $n$ vertices ...
1
vote
1answer
15 views

Finding number of Vertices and Edges of a Graph via Euler's Formula

Let $G$ be a simple $4$-regular connected graph, and suppose that $G$ is planar and has $10$ faces. (A graph is $4$-regular if all of its vertices have degree $4$.) Determine the number of edges of ...
0
votes
1answer
27 views

number of walks of length equal to the size of the edge list [on hold]

Let the graph $G$ and the non-empty list $(e_i ~| ~i \in 1, ... n)$ in $E(G)$ be given. There exists at most one walk of length $n$ in $G$ with $(e_i ~| ~i \in 1, ..., n)$ as its edge list, unless ...
0
votes
0answers
10 views

Cardinality of maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...
0
votes
0answers
13 views

how to find out how many minimum spanning trees does a graph have [on hold]

so i was wondering what method can someone use to find the amount of MSTs in a graph Thanks in advance
0
votes
0answers
10 views

Where is Degree-Diameter Problem table?

Degree-Diameter Problem is a well known problem in graph theory. http://combinatoricswiki.org/wiki/The_Degree/Diameter_Problem I found the table for small diameter and small degree. ...
0
votes
0answers
9 views

Non negative irreducible matrix implies there is a strictly positive power.

How can I proof that a non negative irreducible matrix necessarily has a strictly positive power? By irreducible matrix i understand this http://mathworld.wolfram.com/ReducibleMatrix.html It looks ...
1
vote
1answer
24 views

Matrix irreducibility. Strongly connected graph

I have this theorem from Combinatorial Matrix Theory written by Richard A. Brualdi and others. Let $A$ be a matrix of order $n$. Then $A$ is irreducible if and only if its digraph $D$ is strongly ...
1
vote
0answers
18 views

Serialize Node Graph to integer

Is it possible to serialize a node graph into an integer, in a way that it is recoverable? For example: ...
0
votes
0answers
11 views

relation between regular and distance-regular graphs [on hold]

What is the relationship between regular and distance-regular graphs?
1
vote
1answer
42 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
2
votes
0answers
27 views

What is the Möbius analoge for Ihara's $\zeta$ function?

The Dirichlet series that generates the Möbius function is the (multiplicative) inverse of the Riemann zeta function; if s is a complex number with real part larger than 1 we have $$ ...
1
vote
1answer
24 views

Prove that graph $G$ is bipartite iff every $H\subseteq G$ has linearly independent group of vertices

Prove that graph $G$ is bipartite iff every $H\subseteq G$ has linearly independent group of vertices of size $\leq |V'|/2$. (where $G=(V,E)$ ,$ H=(V',E')$) I managed to prove the first part myself ...
1
vote
0answers
27 views

Induction graph theory - dealing with reducing the problem

I have a general question regarding induction in graph theory. Often I am required to use induction in order to prove a theorm. I have seen a lot of cases in which the reduction of the problem was ...
1
vote
1answer
33 views

graph degrees question (combinatorics)

let it be $(d_1,d_2,...,d_n)$ which represents a series of positive integer numbers, so that $n\gt d1 \gt d2 \gt ... \gt d_n \ge 0$. let it be $K\ge d_1$. given that $(K,d_2,...,d_n,1,1...,1)$ ...
0
votes
2answers
50 views

How do you find the value of n in this example

$$n^{n-2} = 16$$ I know $n = 4$ through trial and error but how do you find $n$ in a conventional manner? I'm basically trying to solve how many nodes are in a tree that has $16$ spanning trees ...
3
votes
0answers
31 views

Book recommendation for network theory

I'm looking for a mathematically rigorous book on Network theory covering topics like entropy, degree distribution, centrality, and regular, random, small-world and scale-free networks. I'm familiar ...
2
votes
1answer
56 views

How to find a maximum matching in this graph

Let's consider this graph: Now I take a matching M that only contains the edge 1. Clearly this matching is not maximum, because I can take the edge 3, so given that: We can easily notice that ...
1
vote
1answer
47 views

Does a $K_n$ with $n$ pendants have a name?

Consider the graph we get by taking the complete graph on $n$ vertices, and then attaching a pendant vertex to each of the $n$ vertices by an edge. Does such a graph have a name, i.e. do such graphs ...
-1
votes
1answer
62 views

How to count the number of walks from $u$ to $v$ in a graph? [on hold]

How can we count the number of walks on a graph from $u$ to $v$? Don't use : If $A$ is the adjacency matrix of the graph, then the $i,j$-entry of $A^n$ is the number of walks from vertex $i$ to ...
-3
votes
0answers
37 views

SimRank Example? [closed]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
0
votes
3answers
41 views

The difference between subgraph and component

I'm studying graph theory right now. I've been reading the textbook and searching the internet, but I still can't understand how subgraph and component are different. Aren't they basically referring ...
-3
votes
0answers
16 views

Let $G$ be a simple graph that is not a forest and has girth $\ge 5$. Prove that the complement of $G$ is Hamiltonian [closed]

Let $G$ be a simple graph that is not a forest and has girth with length of at least $5$. Prove that the complement of $G$ is Hamiltonian. (girth is the length of the shortest cycle of the graph)
2
votes
0answers
37 views

Counting Spanning Trees Needed to cover Edges

This is in the same spirit as this stackexchange post, but I am seeking a more general answer. The goal is, given a graph $G$, give a method of counting the minimum number of spanning trees needed ...
3
votes
1answer
21 views

How to prove vertex-transitivity in regular graphs.

I have problems to prove wheter a regular graph is vertex-transitive or not. For instance, consider the following examples: the generalized Petersen graphs $P_{2,7},\;P_{3,8}$ and the Folkman graph. ...
0
votes
1answer
23 views

Ratio of degrees of nodes in Graph

I have a question regarding to graph and ratio of degrees of nodes in graphs. See the following image: I'm going to find a relation between $A$ and $C$. So, I count all links from $C$ to $B$s $= ...
1
vote
1answer
25 views

Probability of dominating set in random balanced tournament

I'm trying to estimate some probability in a random tournament, and I know that what I have is false, as it leads to contradicting results published some 40 years ago. But I don't know where the ...
2
votes
1answer
32 views

How to answer this graph theory question?

Okay so let me define some terms before I ask my problem: Let $K_n$ denote the complete graph on $n$ vertices with $n\geq 2$ and let $C_3$ be a cycle of length $3$ (a triangle). Suppose $x,y,z$ ...
0
votes
0answers
28 views

A little bit more difficult problem regarding rooted plane trees

A question regarding rooted plane trees bothers me. We know that the number of rooted plane trees with $n$ nodes equals to $n-{th}$ Catalan number, that is $|Tn| = Cn$. But what is this number if we ...
0
votes
2answers
39 views

Computing expectation exercises; using linearity of expectation and iterator random variables

Disclaimer: This is homework that is overdue by, but I do want to understand it and get through it, so any hints or guidance is appreciated This is for an algorithms class currently dealing with ...
1
vote
1answer
19 views

Graph Theory: Conditional Expected Value of Product of two Random Variables

Consider a graph with $n$ vertices, where each edge between any two vertices is independently drawn with probability $p$. Let $D_i$ be the degree of vertex $i$. What is $E[D_i \cdot D_j]$? Here is ...
3
votes
1answer
42 views

Class of graphs with symmetric random walk

Let $(V,E)$ be a graph and let $X_n$ be a random walk on the graph. At every step, the walker at $x$ jumps to one of the neighbors drawn uniformly at random among all the vertices $y$ such that there ...
1
vote
1answer
34 views

Let $G$ be a graph on $n$ vertices, where $n \geq 3$. Suppose that $\Delta(G) \geq n/2$. Can $G$ have more than one component?

Let $G$ be a graph on $n$ vertices, where $n \geq 3$. Suppose that $\Delta(G) \geq n/2$. Can $G$ have more than one component? i did this for $n=3$ $\Delta(G) \geq 1.5$ as $\Delta.1$ component. for ...