0
votes
0answers
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 ?
1
vote
1answer
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$ ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
6
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
3answers
67 views

May directed graph be embedded into manifold?

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

Mathematician who talked about the probability of a “good” graph?

In my undergraduate years, one of my professors always talked about this one mathematician who was talking about "good" graphs and wondered about the existence of such a graph. Apparently this ...
5
votes
0answers
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$. ...
3
votes
1answer
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 ...
2
votes
0answers
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. ...
14
votes
2answers
286 views

Does every “balloon” (dragon, tadpole, canoe paddle) admit a graceful labeling?

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. ...
2
votes
1answer
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 ...
4
votes
2answers
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 & & ...
1
vote
3answers
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) ...
2
votes
1answer
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
3
votes
1answer
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 ...
3
votes
0answers
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 ...
8
votes
2answers
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: ...
0
votes
0answers
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. ...
2
votes
0answers
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 ...
2
votes
2answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
17
votes
3answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
71 views

Triple systems with no six points carrying three triangles

Can anyone please send a link to this article? ...
1
vote
0answers
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 ...
6
votes
3answers
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 ...
3
votes
2answers
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 ...
0
votes
0answers
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 ...
4
votes
2answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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. ...
4
votes
1answer
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 ...
1
vote
0answers
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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.
0
votes
0answers
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 ...
1
vote
0answers
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 ...
2
votes
2answers
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 ...
1
vote
2answers
97 views

Some equivalence relation from flipping binary trees

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 ...
2
votes
2answers
43 views

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.