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

1
vote
0answers
10 views

Approximation for the minimal test cover / minimal group test problem

There are multiple approximation methods I find for the minimal test cover, where approximation is with respect to the size of the test set. However I am looking for approximation which starts with a ...
1
vote
0answers
31 views

Graph theory question about distances

Prove, that for every $n$, a $K(n)$ exists, that no matter how I place $K(n)$ points in the plane, there will always be at least $n$ different distances, that are specified with those points. My ...
1
vote
0answers
20 views

small expected contraction embedding into trees?

I learned FRT theorem for probabilistic metric embedding into trees: For any finite metric d, there exists a distribution over non contracting, small expected expansion tree metrics. The theorem can ...
1
vote
0answers
39 views

Chromatic number for sets of five or more elements

Definition. Given the set $D$ of positive integer numbers, we construct the distance graph for the integers, which vertices are $\Bbb{Z}$ and two numbers $x$ and $y$ are connected if the ...
1
vote
0answers
21 views

zero divisor graphs of a ring

If zero divisor graphs of two finite dimensional algebra are isomorphic does that imply that two algebra are isomorphic as a ring or a vector space?I would also like to know if graph theoretic ...
1
vote
0answers
43 views

What to call a non-edge in a network?

Suppose I have a network with nodes and some edges between the nodes. If node $x$ and node $y$ have an edge, then we say that $(x,y)$ corresponds to the edge between $x$ and $y$. Now suppose that $x$ ...
1
vote
0answers
50 views

Union of two graphs with exactly one common vertex

Does this operation (in the title) have a name? According to the Graph Union operation definition vertex sets of two graphs must be disjoint, however I'd like to define an iterative process of graph ...
1
vote
0answers
18 views

Properties of graph and associated bilinear form

Let $q(x,y)$ be bilinear form on vertexes of connected graph $V$: $q(v_i,v_j) = -1, i \neq j$ and $q(v_i,v_i) = 2$. I had proved that if $q > 0$ then $V$ is tree and if $q \geq 0$ then $V$ is tree ...
1
vote
0answers
80 views

Finding an independent set given partition of a cycle - Lovasz Local Lemma (Alon, Spencer)

Let $G = (V,E)$ be a cycle of length $4n$ and let $V = V_1 \cup V_2 \cup ... \cup V_n$ be a partition of its $4n$ vertices into $n$ pairwise disjoint subsets, each of cardinality 4. Is it true that ...
1
vote
0answers
292 views

Can someone verify my work for finding the following closures?

This is the problem I am currently working on Let R be the relation on the set {0, 1, 2, 3} containing the ordered pair (0,1), (1,1), (1,2), (2,0), (2,2), and (3,0). Find the a.reflexive closure of ...
1
vote
0answers
41 views

Confused about an answer for maximal cliques

I had a question in one of my classes and I am not sure if I misunderstood the answer or if I have the concept wrong in my mind. We were given a graph (see below) and asked whether or not the number ...
1
vote
0answers
31 views

Adjacency of vertices from Prufer sequence

Is adjacency of vertices can be known from Prufer sequence without decoding? Thanks!
1
vote
0answers
38 views

Coset state for non-abelian hidden subgroup problem

On page 14 of his classic paper, Quantum factoring, discrete logarithms and the hidden subgroup problem, Jozsa introduced a function $f$ for the non-abelian hidden subgroup representation of the graph ...
1
vote
0answers
148 views

How to find the number of connected components of a graph by using its 16x16 adjacency matrix?

Good day, I have this exercice that provides me with the 16x16 matrix of adjacency of a graph and it asks me to find the number of connected components of the graph and I need to give a spanning tree ...
1
vote
0answers
53 views

Is there any way one can solve a tangram with n pieces effectively

I suppose that everyone here has played with a tangram, whether fun of not, solving a tangram could be puzzling. I guess most of you are playing with a 7 piece tangram. And to be honest, a 7 piece ...
1
vote
0answers
51 views

Question about u term in graph-related posts

I am studying the solutions posted by Marko Riedel at http://math.stackexchange.com/questions/689526/how-many-connected-graphs-over-v-vertices-and-e-edges. I am porting some of the techniques listed ...
1
vote
0answers
49 views

Spectral gaps of common graphs

I'm looking for the spectral gap of common graphs (alternatively, the mixing time of a (lazy) random walk on these graphs). Asymptotic values are fine. Assume that every node has a sufficient number ...
1
vote
0answers
29 views

What are the requirements for a graph to be a cycle graph of a group?

I've been reading up on cycle graphs, and the different and unique structures that groups produce really interest me. My question is, what is the requirements for a graph to be the cycle graph of a ...
1
vote
0answers
19 views

Is there a standard name for “matching” in bipartite graphs where only vertices belonging to one side have to be matched just once?

Let $G=(L\cup R, E)$ be a bipartite graph (i.e. $E\subseteq L\times R$). A $(*)$ in the graph is a set of edges $M\subseteq E$ such that every vertex in $L$ is matched in $M$ at most once (i.e. ...
1
vote
0answers
95 views

What do you call a network flow problem that allows negative flow values?

I'm trying to solve a relaxed network flow problem, where the relaxation discards the bounds constraints on the network flow (as opposed to a pseudoflow, which discards the flow balance constraints). ...
1
vote
0answers
32 views

Prove that for every $k \geq 1$, there exist a connected graph $G$ of genus $k$

Prove that for every $k \geq 1$, there exist a connected graph $G$ of genus $k$ Here is what I think the proof should be. Let's represent $S_k$ as a regular $4k$- gon as following Define $H$ to ...
1
vote
0answers
20 views

Show that a comparability graph is perfect.

Show that a comparability graph is perfect. I'm trying to be able to prove Dilworth's Theorem from perfect graphs. I'll cite the perfect graph theorem for the complement step. This is the part ...
1
vote
0answers
177 views

Are there any programs like family echo that I can use to map mathematics?

Family echo is an online program that allows one to make a family tree, if nothing is clicked it shows most of the family tree as it is, but if one clicks a name one can see clearly all the ancestors ...
1
vote
0answers
91 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...
1
vote
0answers
71 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
1
vote
0answers
80 views

Infinite connected graph such that every vertex has finite degree

Let $G=(V,E)$ be an connected graph with $|V| \geq \aleph_0$ such that $\text{deg}(v)$ is finite for all $v\in V$. Does this imply that $|V|=\aleph_0$?
1
vote
0answers
27 views

Generalizing interval graphs to higher dimensions

Not every graph is an interval graph, and that makes the notion of interval graph non-trivial. I was wondering whether the following generalization of interval ...
1
vote
0answers
81 views

Principal matrix, Ramsey theorem

Question: Let m be given. Show that if n is large enough, then every n-by-n 0, 1-matrix has a principal submatrix of size m in which all elements above the diagonal are the same, and all elements ...
1
vote
0answers
23 views

Can we know if the Eulerian path that is found in a directed graph is the only path?

I have a genome assembly assignment that reconstructs the genome using an Eulerian path on a de Brujin graph, but there could be multiple solutions, and I'm trying to guess how I would know if there ...
1
vote
0answers
38 views

Show bipartite graph with $m=4$ and $n=4$ is not planar.

I need to show that the 4,4-bipartite $K_{4,4}$ graph is not planar. However, I don't have a clue on where to begin. I figured a constructive proof would suffice, but how can I be sure that that ...
1
vote
0answers
12 views

Does a Matroid's graph not having 3-separation mean its dual doesn't have 3-separation?

Let there be a graph $G$, with a matroid $M(G)$. If there is no 3-separation in $M$, does it imply there isn't one in $M^*$? Any hints would be much appriciated!
1
vote
0answers
73 views

Perfect matching in 3-regular graph.

Prove that each vertex 2-connected, 3-regular graph has a perfect matching. Please give some advice. Thanks in advance.
1
vote
0answers
41 views

If I colour $n$ vertices independently, randomly with $n^{(1-x)}$ colours, why is the size of the colour classes $(1+o(1))n^x$?

By $o(1)$, I mean 'little-o' of $1$. A paper I'm reading uses this result, but I can't see where it comes from. Thanks.
1
vote
0answers
33 views

Choosing which sets of nodes are 'top' and 'bottom' in bipartite graph representations of real-world complex networks.

A bipartite graph is a triplet $G=(\top, \bot, E)$ where $\top$ is the set of top nodes and $\bot$ is the set of bottom nodes, and $E\subseteq\top\times\bot$ is the set of edges. Often real-world ...
1
vote
0answers
107 views

Comparison with the greedy algorithm

Consider the following algorithm to vertex coloring: First find a maximal independent set of vertices and color these with the color 1. Then find a maximal independent set of vertices in the remaining ...
1
vote
0answers
32 views

Expected chromatic number

If $ G = (V, E) $ is an undirected graph where each edge is included with probability $ p \in [0,1] $ is there a way to calculate $\mathbb E[\chi (G)]$ using elementary methods? Or at least establish ...
1
vote
0answers
25 views

Strongly regular directed graph and its complementary graph..

I'm reading a paper (Art Duval) about generalizing the strongly regular idea to directed graphs.. anyway, the lemma is: Also, to be clear, the parameters are: n - number of vertices, k - valency, u - ...
1
vote
0answers
75 views

Is there any efficient progam or software to calculate the fractional chromatic number?

The fractional chromatic number $\chi_f(G)$ is a generation of the chromatic number of a graph $G$. It can be formulated as a linear programming question: Let $\mathcal{I}(G)$ be the set of all ...
1
vote
0answers
26 views

Plotting weighted nodes around a center

I am trying to plot nodes around a central node dynamically by weights of similarity. I have the weight of each node to every other node. I need to display the arrangement in such a fashion that it ...
1
vote
0answers
41 views

Good and thorough online and/or free Matroid Theory references?

I'm studying a course on Matroid theory. Sadly, I can't really afford buying the textbook, so I only use the lecture notes, which aren't enough for me. Are there any good and thorough online and ...
1
vote
0answers
61 views

biconnected graphs - st-numbering intution

Looking at this paper, the algorithm is done in two phases. First phase: Do a DFS search, compute the spanning tree with p[v] representing parent of v, compute the lowest ancestor (closest to the ...
1
vote
0answers
53 views

Expected Max Pseudotree Size

I'm working on a problem where I need to calculate the expected maximum pseudotree size in a randomly-generated pseudoforest with $n$ nodes. Expected maximum value is of course: $$ E(x) = ...
1
vote
0answers
44 views

Deviation of number of cycles of length 4 in Erdős–Rényi random graphs.

I'm working on my homework and can't find any relevant information for this problem. Problem: Let $G(n, p)$ be Erdős–Rényi random graph. I need to find deviation of number of cycles of length 4 in ...
1
vote
0answers
51 views

Inequality to bound $\sum_i a_i b_i - \sum_i c_i d_i$ (harmonic eigenfunction/graph) type sum with constraints

We have a homogeneous graph $G = (V,E)$ with a function $f:V\rightarrow \mathbb{R}$. We define the following modulus: $\displaystyle \omega(s) = \sup\{f(x)-f(y) \ | \ |x-y|=s \}$ and wish to lower ...
1
vote
0answers
98 views

Induced cycle of odd length in a large graph

I'm trying to prove the following result in order to solve a different problem but I'm stuck; however I'm not sure if it is true, so I'll pose it as a question; Suppose we have a triangle-free ...
1
vote
0answers
512 views

Proof of Hamilton Cycle in a Complete Bipartite Graph

For a complete Bipartite graph K(m,n) has a Hamilton cycle if and only if m=n. I want to know if the following proof technique is correct. My proof will consider using proof by contradiction. Assume ...
1
vote
0answers
32 views

What is $F_P$ and $E(P)$?

I'm reading Handbook of Graph Theory: At this section, he speaks about $F_P$ and $E(P)$. It's not really clear what they are. I guess there is enough context for someone to answer me but if ...
1
vote
0answers
30 views

Hypergraph coloring

I hawe the following task: Decide if all 4-uniform hypergraph with fourteen hyperedges can be colored with 2 colors. I think that the answer is yes, but how can i prove it?
1
vote
0answers
23 views

Potentials and Markov Processes

Given a resistive electrical circuit $G$, i.e. a graph with nonzero weights attached to each edge whose reciprocal we call the "resistance," we can define a reversible markov chain on the graph, ...
1
vote
0answers
61 views

Prove $\lambda=\min_{i = 1,\ldots, n}\max_{0 \le k \le n-1}\left(\frac {p_i(n)-p_i(k)}{n-k}\right)$

Prove the minimum directed cycle mean cost satisfies: $\lambda = \min_{i = 1,\ldots, n} \max_{0 \le k \le n-1} \left(\frac {p_i(n) - p_i(k)} {n-k}\right)$ using the Bellman-Ford algorithm. Let ...