Use this tag for questions in graph theory. Here a graph is a collections of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
3
votes
2answers
39 views
Whose full bipartite and 3-partite graphs are eulerian/hamiltonian graphs?
Which full bipartite ($K_{r,s}$) and 3-partite ($K_{r,s,t}$) graphs are eulerian/hamiltonian graphs?
What I have found so far:
bipartite/eulerian $\rightarrow 2|r \land 2|s$
...
0
votes
1answer
21 views
Intersection and Union of sub graphs
can anyone phrase a common definition for the union and intersection for below case.
Actually I am looking for mathematical expression in mathematical notations.
For example if I want to do $G_1 ...
0
votes
2answers
56 views
Prove that for any graph G, there are at least $\chi(G)$ vertices with $degree\geq \chi(G)$ − 1.
Prove that for any graph G, there are at least $\chi(G)$ vertices with $degree\geq \chi(G)$ − 1.
$\chi(G)$ chromatic number of graph $G$.
2
votes
2answers
91 views
Tree pruning question…
all. I'm facing the question:
"A chain letter starts when a person sends a letter to five others. Each person who receives the letter either sends it to five other people who have never received it ...
1
vote
1answer
30 views
Is this a complete graph
I know a complete graph must have a edge between every pair of vertices, so I just wanted to make sure whether the below was a complete graph or not? I am guessing it isn't because there is no edge ...
0
votes
1answer
77 views
How to prove Petersen graph has no Hamiltonian cycle?
How to prove Petersen graph has no Hamiltonian cycle?
My working
$step \ 1.$ first assume that there exists a cycle.
$step \ 2.$ now take a-b-c three continuous node from cycle,than delete node b ...
2
votes
1answer
67 views
$\chi(G) \cdot \chi(\bar{G})\geq n$ [duplicate]
Prove that $\chi(G) \cdot \chi(\bar{G})\geq n$
$\chi(G)$: number of colors required for a graph $G$.
Here $\bar{G}$ is a graph that consists of all the edges that are not in $G$.
0
votes
0answers
30 views
Signed incidence matrix determinant and spanning tree
$G=(V,E)$ is a directed graph with $n$ vertices and $m$ edges, $n \geq 2$. $F \subseteq E$ and $|F| = n -1$.
$Q$ is the $n \times m$ signed incidence matrix of $G$ over indeterminates $x_e$ with $e ...
3
votes
3answers
104 views
A puzzle about graph coloring.
Let $G$ be a graph with three disjoint triangles(i.e. the graph is not connectd and has three connected components each of which is a triangle). If each vertex of G is assigned a red or a green color, ...
2
votes
2answers
50 views
difference between “minimal” and “minimum” edge cuts.
I was going through the topic about connectivity of graphs. There it was mentioned about the terms "minimum edge cut" and "minimal edge cut". I know both are the sets of edges if removed from the ...
2
votes
0answers
21 views
how the number of steps needed depends on the number of nodes and depends on the transmission range?
I run the consensus algorithm, and for each round k, we record the norm of the disagreement vector(|(|δ(k)|)|>〖10〗^(-6)). We stop, at a predefined value|(|δ(k)|)|>〖10〗^(-6) and we call this ...
1
vote
2answers
63 views
Adjacency matrix
Let $G$ be any simple and undirected graph. Let $A$ be the adjacency matrix of $G$.
1) Let $B$ be the number $\tfrac16\mathrm{tr}(A^3)$. What does $B$ count? That is $B$ counts the number of....?
2) ...
2
votes
1answer
45 views
self-centered property of complement of a self-centered graph
I was working out on a problem. Came out with a result that $C_n$ is self centered graph, its complement is also self centered, infact 2-self-centered. Worked out on other few graphs which are self ...
2
votes
1answer
34 views
For any graph G, How do I find the algorithm that returns the permutation of vertices with minimum bandwidth?
Given a graph $G$, is there an algorithm that returns the ordering of vertices with minimum bandwidth?
The bandwidth of an ordering of vertices, $f: V(G) \rightarrow \{1, 2, \ldots, |V(G)|\}$ is ...
2
votes
3answers
116 views
Showing that no Hamilton Circuit exists
I was confused about a certain concept and I was wondering if I could get some help.
There were three points that were made in my textbook to show that a graph does not contain a Hamilton circuit:
...
0
votes
0answers
54 views
Find the articulation point in these graphs
I want to find the articulation point (also called bridge?) of these graph
Complete
For this one, I have that there is no articulation point since each vertex is connected with n vertices. if you ...
1
vote
1answer
39 views
Network Analyses with Subgraphs
Suppose that I have a graph and I divided it to subgraphs which can be overlapping. I want to use these subgraphs in network analyses like centrality calculation, community detection etc. instead of ...
1
vote
0answers
25 views
Independence and the size-biased degree distribution in the configuration model
I'm teaching a course on complex networks using M.E.J. Newman's Networks: An Introduction. There is a claim in the book that is not really justified, and I don't know how to prove it.
Background and ...
0
votes
1answer
24 views
Existence of a kernel in induced subgraph
Theorem (The Dinitz Problem - M. Aigner, Günter M. Ziegler: Proofs from THE BOOK (4th edition)):
Consider $n^2$ cells arranged in an $(n × n)$-square, and let $(i, j)$
de- note the cell in row ...
2
votes
0answers
28 views
phrasing union and intersection of graphs (cycles)?
If I am having cycle graphs for example $G_1, G_2, G_3$. then how can I phrase union and intersection of adjoining graphs (i.e. having at least one common node with other) in mathematical notations.
...
1
vote
0answers
18 views
Delocalization of eigenvectors in Expanding Graphs
Given an adjacency matrix A, can we say something about whether the eigenvectors corresponding to its highest(or second-highest) eigenvalues are delocalized ? By delocalization I mean that every ...
2
votes
0answers
234 views
The Dinitz Problem - proof
This theorem is the one that the proof is for
Consider $n^2$ cells arranged in an $(n × n)$-square, and let $(i, j)$
de- note the cell in row $i$ and column $j$. Suppose that for every
cell ...
0
votes
1answer
43 views
Show that G is Hamiltonian for $n \ge 4$ with $V = {2, 3, … , n}$
for all $ n \ge 4$ show that G=(V,E) is an hamiltonian Graph iif n is odd. also show that G is not hamiltonian if n is even. The graph is non-oriented
$V = {2,3,...,n}$
$E = {i,j} \in V X V | ...
1
vote
1answer
55 views
Graph with closed path of length $\leq 4$.
Assume $G=(V,E)$ with $\forall v \in V: \deg(v) \geq d$ and $d \geq 2$ such that $|V|= d^2$. Then there is a closed path of length $\leq 4$ in $G$.
Some hints would be helpful :)
3
votes
1answer
62 views
What is the fastest computational graph theory package?
What is the fastest computational graph theory package with respect to executing algorithms and computing graph theoretic data?
I am aware of this related question, which requests graph theory ...
0
votes
1answer
29 views
Difference between hyper graph to bipartite graph
Whats the difference between a bipartite graph and a hyper graph ?
Can i assume a directed hyper graph is a directed bipartie graph ?
1
vote
1answer
73 views
How can i convert to the undirected matrix to an directed matrix?
Here A square matrix and first figure(AU) shows undirected connection graph and second one shows directed one.Assume that only i have Au metrix and how can i create Ad metrix from Au matrix in ...
2
votes
0answers
14 views
Number of bridges in a random graph $G(n,p)$.
What can we say about the number of bridges in a $G(n,p)$ random graph? For example, can we estimate the expected number of bridges in terms of $n$ and $p$?
3
votes
1answer
63 views
Proving two graphs are isomorphic
I need to prove that the following two countable undirected graphs $G_1$ and $G_2$ are isomorphic:
Set of vertices of $G_1$ is $\mathbb{N}$ and there is an edge between $i$ and $j$ if and only if the ...
1
vote
1answer
31 views
What's the dual graph of the plane graph of order 2 and size 0?
Consider the plane graph consisting of 2 vertices and no edges. It has one face and no edge, so its dual is the trivial graph. On the other hand, it has two vertices, so its dual should have two ...
1
vote
0answers
18 views
Rating and Scoring Graphs based on physical properties
i am busy working on a project related to L-systems. The basic idea is to generate graphs from these L-strings and rate them based on some physical traits, such as self similarity....
Is there any ...
0
votes
1answer
46 views
Counting graphs with even degrees! Trouble with formula!
There is one topic about "Counting graphs with even degrees" here that tell something about edge space, vector space, cut space and ...
I have a graph exam tomorrow, and there is a problem that said ...
2
votes
1answer
38 views
Integers and Rectangles
Interesting problem of rectangles and integers is discussed on Cut the Knot resource
Theorem: Whenever a rectangle is tiled by rectangles each of which has at least one integer side, then the ...
2
votes
1answer
25 views
Number of faces of plane Graph
How do i begin this proof?
Let $G$ be a simple connected triangle-free plane graph with at
least three vertices. Prove that $f \leq n-2$.
1
vote
1answer
44 views
Prüfer sequence for an order-2 tree?
All the algorithms for constructing a Prüfer sequence state that the input is a tree, but none give any output corresponding to an order-2 tree.
And Wikipedia gives this definition:" A Prüfer ...
3
votes
1answer
55 views
number of paths between [i] and [j] on a directed unweighted cyclic graph?
Given a directed unweighted cyclic graph G consisting of up to 30 nodes and 30 edges find number of paths between i,j for all i,j in G
If there are infinite number of paths detect it
In ...
4
votes
1answer
60 views
Knight tour problem??
Consider an n × n chess board. For what values of n is it possible to find a knight’s tour around the
board which uses every possible move just once (in one direction or the other).
Here on what ...
2
votes
1answer
29 views
Is the expected number of components in a random graph $G(n,p)$ a decreasing function of $p$?
Let $X$ be the number of connected components in $G(n,p)$. If we fix $n$ and vary $p$, is $E(X)$ a decreasing function of $p$? I "feel" that this should be right because as $p$ increases there are ...
0
votes
2answers
29 views
Vertex between other vertices
I'm reading a paper on graph theory (On Disjoint Paths in Planar Graphs) and in an algorithm they define the set N to be the vertices between S1 and S2. But I'm wondering what exactly defines a ...
3
votes
1answer
180 views
$k$-partite spanning subgraph
I found an interesting problem:
Prove that for every $k>1$ any loopless undirected graph $G$ contains a $k$-partite spanning subgraph $H$ such that: $\left( 1-\frac{1}{k} \right)\deg_G(x) \le ...
0
votes
2answers
55 views
Create a Generating function
Let $P$ be the set of permutations all of whose cycles are of even length. Prove that the exponential generating function for $P$ is $\dfrac{1}{\sqrt{1-x^2}}$.
1
vote
1answer
39 views
Are Hamiltonian Paths still NP-Complete if you are allowed to revisit vertices?
If you have a one or more Hamilitonian cycles in a graph, but you remove the restriction of only being able to visit a vertex once, then is it still an NP-Complete problem?
That is, is there no ...
2
votes
0answers
67 views
Teleporting random walk
Given a directed graph $G = (V,E)$, to define a random walk on $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution (as mentioned in this paper)
I used a one ...
0
votes
0answers
36 views
Proof of Sperner's Lemma
I am looking for a concise and mathematically robust proof of the Sperner's Lemma.
The easiest proof I found so far is Math Pages Blog, but I don't get it without few details.
Following is the proof ...
4
votes
0answers
67 views
What can be said about the number of connected components of $G(n,p)$ random graphs?
By a $G(n,p)$ graph we mean a graph on $n$ vertices, all possible edges are independently included randomly with probability $p$.
What can be said about the number of connected components? For ...
3
votes
1answer
23 views
Names and algorithms for subgraphs with smallest neighbourhoods
I'm curious about some terminology for graphs and the existence of an algorithm. Let $G$ be a graph and $H \leq G$ a subgraph. Is there a name given to $H$ if $|N(H)|$ is minimum over all subgraphs ...
0
votes
1answer
30 views
can plane graph be split?
When I consider a cycle graph (directed graph), I think the removal of some desired edges is logical.
But, If I refer that graph as a plane graph, that mean as a face
then Do the removal of some ...
0
votes
2answers
30 views
How can it be proved that each vertex can be at most in one strongly connected component in a directed graph?
How can it be proved that each vertex in a directed graph will exactly be in at most one strongly connected component? I do not see it in the graph below which I think contains a couple of connected ...
3
votes
1answer
25 views
Hypergraph Colorability
I'm interested in hypergraphs for which there are known (nontrivial) lower bounds on the chromatic number. If someone could point me to existing literature (survey papers etc) on this topic that would ...
0
votes
0answers
15 views
What is the computational complexity of END-OF-THE-LINE when we require the output node to be connected to the input node?
The problem END-OF-THE-LINE is:
Let $G$ be a directed graph such that each node has in- and out-degree at most $1$. Given a node $g$ of $G$, either (1) decide that $g$ is a balanced node, or (2) ...
