# Tagged Questions

11 views

### Geometric dual graph

It is well known the notion of geometric dual graph. Let $G^*$ be the geometric dual of a planar graph $G$. I need the proof that $(G^*)^* \cong G$ , where can I find it ?
18 views

### Kirchoff Matrix -Tree Theorem

I'm reading a proof of the Kirchoff Matrix -Tree Theorem: If $G$ is a simple connected graph, $D$ the diagonal matrix with the vertices' degrees and $A$ the adjacency matrix, then in $M = -A+D$ ...
52 views

### Determinant of identity minus adjacency matrix

Let $M$ be the adjacency matrix of a directed graph $G$. Is there any known relation between $\det(\textrm{id}-M)$ and the cycles of $G$? It is easy to see that if $G$ is acyclic then this ...
33 views

### proof of Konig's Theorem for bipartite graphs from Menger's Theorem

Could someone provide me with a good reference for a proof of Konig's Theorem for bipartite graphs from Menger's Theorem? Konig's Theorem is as follows: For a bipartite graph $G$, the maximum size ...
65 views

### Where can I download the approx 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof?

Where can I download computer representations of the approximately 1500 Appel-Haken reducible configurations in the Four-Color-Theorem proof? The Wikipedia article ...
39 views

### Clustering analysis of a weighted graph

My data consists of a large weighted undirected graph of $n$ nodes. I need to group the nodes into $m$ clusters ($m < n$), such that nodes in a cluster are connected with heavy weights. What ...
67 views

### May directed graph be embedded into manifold?

May directed graph be embedded into manifold?How ?and what is the condition?
176 views

32 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$. ...
78 views

### Textbooks on graph theory

I've read the textbook Groups and Their Graphs by Grossman, and I'm interested in learning more about graphs. I know about O. Ore's book in the same series (Graphs and Their Uses), but I'm interested ...
15 views

### Sampling from a graph

Suppose you have a graph $G=(V,E)$ that is unobservable globally and you wish to take a sample from the vertices of that graph to infer something about its global properties from local properties. ...
286 views

8/18/14 Edit: If anyone has a copy of a related reference, then I would be happy to see it. For now, I am accepting the answer below and considering the question answered in the affirmative: Yes. ...
55 views

### Mathematics of genealogical trees

I really searched a lot but did not find anything meeting my needs: A place where questions of genealogy, especially the structural and combinatorial analysis of genealogical "trees" of descendants ...
78 views

### Graph that represents logical reasoning

The proof of a statement $X$ in terms of assumptions $A$, $B$ and $C$ can sometimes be represented using a directed graph:  \begin{matrix} & & X\\ & \nearrow & & ...
125 views

### Choosing good textbooks in linear algebra, analysis and graph theory

I need some advices to choose good undergraduate textbooks in LINEAR ALGEBRA, ANALYSIS and GRAPH THEORY. I found: Gilbert Strang // Introduction to Linear Algebra - Welleslay Cambridge Press (2009) ...
101 views

### Easy to read books on Graph Theory

I was asked to read about Graph Theory. First got the book "Graph Theory with Applications" by Bondy and Murty. As a Computer Science student its becoming difficult to read and understand. Then I ...
97 views

### When graph theory cannot model the most basic problem in wireless networks. Why?

I have a set of wireless links. These links are denoted by $\mathcal{L}=\{\ell_1, \dotsc, \ell_n\}$. Every link $\ell_i$ is composed of one transmitter $s_i$ and one receiver $r_i$. Initially, all ...
111 views

### Characterizing a certain set of matrices arising from binary trees

Suppose I have a binary tree, like v1 v4 \ / -------- / \ v2 v3 I can write a matrix for this tree whose $(i,j)$th ...
46 views

### Automorphism group of a bipartite regular graph

Showing an automorphism group of complete bipartite graph $K_{n,m}$ is easy. I'm wondering if there is an classification of automorphism groups of bipartite regular graphs. Did anyone heard something ...
31 views

### Graph algebra papers

The following graph multiplication appears to be quite natural: Let $g_1=(V_1,E_1)$ and $g_2=(V_2,E_2)$ be two graphs ($V_i$ are sets of vertexes and $E_i$, sets of edges). Intuitively, the product I ...
28 views

### An interleaved path of arrows in a category/digraph

In what I am doing now, a slightly strange concept emerged; My objects are sequences of arrows $\{f_i\}_{i=1}^{n}$ in a small category such that for every $1\leq i\leq n-1$, there is an arrow from the ...
37 views

### Reversing a random walk on a hypergraph

I'm looking for resources (books, papers, etc) that will suggest how to reverse random walks on an invariant directed hypergraph. If you're curious, more details are below. In my problem, I allow a ...
58 views

### existence of spanning trees in complete graphs implies choice?

it is known that the existence of spanning trees in arbitrary (connected) graphs implies the Axiom of Choice. I was wondering if this result still holds if we restrict ourselves to spanning trees of ...
46 views

### A stronger condition than planar graph?

Is there a name for this condition on a graph: a graph that can be embedded in the plane (planar), in such a way that of its univalent vertices do not lie inside any face? So, one can think of this ...
116 views

### Mathematicly Untangeling Untangle.

I have a new addiction, I play Untangle to often, and i am wondering what is the mathematics behind it. some free games: (but be warned highly addictive) Javascript: ...
37 views

### Maximum independent set problem

I need to study about the maximum independent set problem in graph theory. I need to study the $P_t$ free graphs and many other such variants and look up their maximum independent set characteristics. ...
49 views

### References for chromatic symmetric functions of hypergraphs

Define a hypergraph to be a pair $H = (V,E)$ where $V$ is a set of vertices and $E$ is any set of subsets of $V$ called edges. Thus if every edge $U \in E$ has only two elements, then the hypergraph ...
83 views

### Text on Group Theory and Graphs

A student and I are going to investigate the use of group theoretic techniques in graph theory. What are good texts in this area (introductory and otherwise)? We are particularly interested in ...
22 views

### looking for hypergraph decompositions

there are many thms for/types of graph decompositions. in contrast, am looking for various types of hypergraph decompositions...? also esp interested in graph analogs that translate somehow eg ...
21 views

### Lp graph theory

Let $X=X\left(V,E\right)$ be a graph. Let $f$ be a function on $X$. Let $1\leq p<\infty$. If we define $L^{p}\left(X\right)$ to be the set of all functions $f$ on $X$ such that ...
80 views

### Usefulness of eigenvalue centrality

Question for the network theorists/computer scientists: I heard that the eigenvalue centrality is "useless" and "too sensitive to jump behavior" for directed graphs. $\bullet$ What does this mean ...
284 views

### Results in graph theory proved using other areas of math, and vice versa

I'm curious about learning graph theory, as it seems to pop up in some unexpected places. In order to get a partial feel for the subject, I was wondering if anyone could point me to some survey ...
26 views

### Network component detection

Suppose I have a (directed) graph with nonnegative edge weights. I would like to separate the graph into what you might call "$\epsilon$-components", that is, a partition $\{ V_i \}$ of the set $V$ of ...
71 views

117 views

### Is D.B.West's Introduction to Graph theory a good book to start?

I am studying for International Olympiad for Informatics (IOI) and I have to have a good understanding of Graph Theory . a teacher suggested reading Introduction to Graph Theory by D.West. Is it a ...
166 views

### How much topology for graph theory?

I am writing a thesis in the context of descriptive complexity in theoretical computer science and therefore need to study a little bit of graph theory. My background is not mathematics but computer ...
67 views

### Graphs with a polynomial number of shortest paths between any pair of vertices

Let $G$ be a simple undirected graph, and let $s$ and $t$ be two arbitrary vertices of $G$. Even for some rather restricted graph classes, the number of shortest paths between $s$ and $t$ can be ...
31 views

### Reference for Body-and-bar or Body-and-hinge frameworks

I'd like a comprehensive reference for the mathematical theory behind body-and-bar and body-and-hinge frameworks (brief intro), possibly with an emphasis on the latter. There are a large number of ...
145 views

### Maximum edges in a square free graph

Square free graph : Graphs with minimum cycle length greater than 4. Question : What is the maximum number of edges possible for a square free graph $G(V,E)$ given that $|V|$ = n. Is it of the order ...
45 views

### Filling a infinite colored graph with basis

This is a mathematical question raised from engineering and physics: Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For ...
43 views

### A Survey on Rota's Conjecture

I am looking for a survey on Rota's Conjecture (1970). I am more interested in geometric aspects of the conjecture and any geometric content related to the conjecture. Any reference would be helpful. ...
110 views

### Where can I find a proof of Tutte's theorem?

I dislike the proof of Kuratowski's theorem in my textbook, but the book mentions a theorem of William Tutte: Theorem: A graph $G$ is planar if and only if the conflict graph of each cycle of ...
49 views

### Mathematical research on ground state configuration of ising model

I want to do mathematical research (algorithm construction and mathematical analysis) on ising model ground state configuration. From what I know, the state of art research is using graph theory ...
47 views

### Does the notion of graph with vertex multiplicity exist?

I need to use graphs where each vertex gets a natural number, $b(v)$, its multiplicity. These numbers indicate how many 'replications' of the vertex we have. It is actually a way to write in a ...
72 views

### material for graph theory practice

How to practice more on graph theory. My course book is Graph Theory by Narsingh Deo but still I want to go in more depth.Please refer links or preferable book.
73 views

### First event in a straight skeleton

Is there a simple geometric criterion to check whether the first event in (the wave propagation of) a straight skeleton is an edge event or a split event? The literature I could find is computational ...
53 views

### Types of symmetry for combinatorial graphs

Let $G$ be an undirected, connected graph without loops. Let's call $G$ symmetric iff it has a non-trivial automorphism (that is a permutation $\pi : V(G) \rightarrow V(G)$ – which is not the ...
58 views

### Generalizations of colorability

It is fun to recognize that the $n$-colorable graphs are exactly those graphs $X$ in the category of simple graphs with an homomorphism to the complete graph $K_n$. Question 1: Are there other ...
I know almost nothing in combinatorics, so this question might be very easy, or well-known. Fix a number $n$. We will consider rooted planar binary trees with $n$ leaves. We will distinguish between ...
### Connected cubic $s$-regular graph
Let $X$ be connected cubic $s$-regular graph then $|Aut(X)| = 2^{s-1}\cdot 3\cdot |V(X)|$. I want a reference for proof.