2
votes
1answer
59 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
79 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
105 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
24 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
29 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
10 views

Edge density of infinite graphs

What notions of edge density of infinite (not necessarily countable) graphs exist? I do know the notion of upper density, which is not much more than saying "an infinite graph is dense if it has large ...
0
votes
0answers
25 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
28 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
55 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
44 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
102 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
36 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
38 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
58 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
0answers
17 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
18 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 ...
1
vote
1answer
56 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 ...
16
votes
2answers
261 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
25 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
58 views

Triple systems with no six points carrying three triangles

Can anyone please send a link to this article? ...
1
vote
0answers
84 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
142 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
54 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
24 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
103 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
44 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
42 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
99 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
43 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
41 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
68 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
71 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
47 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
53 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
84 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
39 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.
2
votes
0answers
59 views

How can I understand the Hadwiger conjecture?

I would like to understand the Hadwiger conjecture and I would like to read books that will allow me to both understand it and also get a grasp of the theory it is related to. Regards
0
votes
1answer
43 views

Let $G$ be bipartite, what is $\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$

Let $G$ be a bipartite graph. Let $X,Y$ be the two partite sets of $G$. Suppose further that $N(X)=Y$. Consider the problem of finding: $$\min\{|X_0|:\,X_0\subseteq X\,,N(X_0)=Y\}$$ What are some ...
2
votes
2answers
206 views

Books in Combinatorial optimization

I wrote Combinatorial optimization in the title , but I am not sure if this is what I am looking for. Recently, I was getting more interested in Koing's theorem, Hall marriage theorem . I am ...
3
votes
1answer
26 views

Set of nodes to remove to leave zero edges with maximal summed node values.

I'm primarily looking for some help for a graph theory question. What I'd like is a reference that deals with this particular question, or background knowledge if this question is already well-known ...
0
votes
0answers
37 views

Graphs formed by adding vertices to the circular layout of the complete graph $K_{n}$.

Beginning with the complete graph $K_{n}$ for $n\geq 3$ and construct a new graph $G_{n}$ from it such that $G_{n}$ contains every vertex from the circular graph layout of $K_{n}$. For instance, if I ...
1
vote
1answer
66 views

Number non self avoiding closed walks surrounding some point

While studying some Peierls-like arguments in statistical physics I thought about the following problem: We have some 2d-integer lattice like this, for simplicity infinite in all directions. Now fix ...
0
votes
0answers
22 views

A book (or tutorial) on probabilistic networks

I use the term "probabilistic networks" to describe graphs for which one or more link lengths are defined as random variables. Specifically, I'm looking at optimization problems on these graphs. An ...
3
votes
1answer
115 views

Graph clique problem

I'm not sure to what degree this is a graph problem, and algorithms question, or what, but I'll give the setup: I have a simple undirected graph given in the form (for example) ...
1
vote
0answers
60 views

Is there a common notation for the labelled degree of a vertex?

Let $G$ be an undirected graph with labelled edges. The labelled degree of a vertex $v \in V(G)$ is the number of edges incident to $v$ with distinct labels. The definition of the labelled degree ...
3
votes
1answer
56 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 ...
13
votes
3answers
664 views

Exceptional books on real world applications of graph theory.

What are some exceptional graph theory books geared explicitly towards real-world applications? I would be interested in both general books on the subject (essentially surveys of applied graph ...
4
votes
2answers
85 views

The Dinitz problem

I would like to ask if someone knows about good books or online articles about The Dinitz problem or maybe someone can explain the problem a little. Consider $n^2$ cells arranged in an $( n \times ...
1
vote
1answer
167 views

Introductory Level Books for Graph Theory

Can anybody please suggest some good introductory level text books on Graph Theory ? Preferably those which don't really require a great pre-requisite background on discrete mathematics, but rather ...
1
vote
2answers
55 views

Name for a path with least number of vertices.(Graph Geodesic)

What is the name given to a path between to points that is of length equal to the distance from those two pints. Sorry to bother you but the definition was on a book I no longer have.