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

Software for computing n-Clique, n-Clan, n-Plex?

I am studying graph theory and complex network into details, I would like to ask if some one could help providing a useful (academic) tools or some good tools for computing n-clique, n-clan, n-core, ...
0
votes
0answers
11 views

Cycle with negative length in a directed graph

Consider a network $G = (V,A)$. Suppose that node $v_1$ has no incoming arrows and that for every $v_j \neq v_1$ there exists a path from $v_1$ to $v_j$. Show that $G$ has a cycle with negative length ...
1
vote
1answer
17 views

K-Clan detection based on a given connected Graph

I have the following definition of the K-Clan: A k-clan is a k-clique where the diameter of the corresponding sub-graph is at most k. and here according to the graph bellow I do not know why 135 is ...
0
votes
2answers
20 views

Find a graph with critical vertices and without critical edges.

A vertex or an edge is a critical element of a graph G if its deletion would decrease the chromatic number of G. Obviously such decrement can be no more than 1 in a graph. A critical graph is a ...
0
votes
0answers
26 views

Complete Planar Bipartite Graph

Determine exactly the values of $m$ and $n$ for which the complete bipartite graph $K_{m,n}$ is planar. I have tried doing this by drawing different complete bipartite graphs and just using guess and ...
0
votes
0answers
14 views

What term do I use to distingush between a data visualisation graph and a nodes and edges graph?

When googling, I have a problem distingishing my searches between a data visualation graphs (eg. scatter plots, bar charts etc), and node and edge graphs. The term 'directed graph' can be used, but ...
0
votes
1answer
10 views

Complete Bipartite Planar Graph

Determine exactly the values of $m$ and $n$ for which the complete bipartite graph $K_{m,n}$ is planar. I have tried doing this by drawing different complete bipartite graphs and just using guess ...
2
votes
2answers
43 views

the number of copy of 6-cycles in petersen graph

the number of copy of 6-cycles in petersen graph.I know that Petersen graph has ten copy of 6-cycles but I can't prove it.
1
vote
1answer
23 views

Determine all graphs with size $3n-5$ such that $G-e$ is planar for every edge $e$ of $G$.

I believe I have this one, but I wanted to see if my reasoning is sound since I can only find 1 such graph with this property. Let $G$ be a graph of order $n$. First, if $G-e$ is planar for every ...
1
vote
0answers
10 views

On bounding the diameter of a undirected simple connected graph

This may be a something already there in literature but I am unable find it: Given an undirected simple connected graph $G$ whose vertices has a degree at-least $d$ and $\ge c n^2 $ edges, where $0 ...
0
votes
0answers
7 views

Is unycyclic, a doubled edged graph obtained from two cycles wich have a common edge?

Let $G_I = (E_I, V_I)$ and $G_J = (E_J, V_J)$ two cycles. How could I prove that : If I want to obtain a double edged graph $G$ from the two cycles, $G_I$ and $G_J$, so that $G_I$ and $G_J$ have an ...
2
votes
0answers
25 views

Maximum independent sets of $k$-partite graphs

Consider a $k$-partite graph $G=(V,E)$. This means that its vertices can be partitioned into $k$ different independent sets, say $V_1,\dots, V_k$. Assume further that $|V_1|=\dots = |V_k|$. Under ...
0
votes
0answers
13 views

Inflow and outflow of Traffic graphs

For my bachelor thesis I am making a model for calculating a distribution of traffic in a network/graph given the delay on the links of the graph. I have written a Matlab program, and it seems to ...
0
votes
1answer
17 views

Construction of graph Laplacian

I have a weighted undirected graph, and all the edge-weights are non-negative. According to the definition of the graph Laplacian matrix, $L=D-W$. In literature, I found that $D$ is known as degree ...
0
votes
1answer
25 views

Colour Critical Graph Proof

Let $G = (V, E)$ be a simple graph. We call $G$ colour-critical if $\chi(G) > \chi(G\setminus v)$ for all $v \in V$. Prove that if $G$ is colour-critical with $\chi(G) = k$, then $d(v) \geq k − 1$ ...
3
votes
1answer
20 views

Explanation of exam question on what looks like the handshake lemma.

The question goes as follows: The total degree of an undirected graph G = (V, E) is the sum of the degrees of all the vertices in V. Prove that if the total degree of G is even then V will contain an ...
0
votes
1answer
41 views

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

I overheard someone talking about using the Manhattan 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
57 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
30 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
31 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
38 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 ...
-8
votes
0answers
49 views

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

I dont know how even think about it. Anyone? thanks
2
votes
1answer
47 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. ...
1
vote
2answers
17 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
38 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
23 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 ...
2
votes
1answer
31 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
20 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. ...
4
votes
1answer
24 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
25 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
40 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
17 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
17 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
31 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
11 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
29 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
28 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
32 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 ...