Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

3
votes
2answers
223 views

Can the Vertices of cubic graph be partitioned into and induced cycle and a forest?

Let $G$ be a $2$-connected $3$-regular graph. Can $V(G)$ be partitioned into $V_1$ and $V_2$ where $G[V_1]$(the induced subgraph on $V_1$) is a cycle of $G$ and $G[V_2]$ is a forest (Acyclic ...
2
votes
1answer
137 views

Is the set of edge of a cubic graph the union of a cycle and and an Acyclic graph?

Let $G$ be a $2$-connected $3$-regular graph. Is it true that $E(G) = E_1 \cup E_2$ where $G[E_1]$(the induced subgraph on $E_1$) is a cycle of $G$ and $G[E_2]$ is a forest (Acyclic subgraph) of $G$? ...
2
votes
0answers
79 views

Counting regular Hypergraphs

The problem of counting regular graphs on $n$ vertices is notoriously hard. It seems like counting regular hypergraphs on $n$ vertices should be much easier (I am placing no uniformity condition). ...
0
votes
1answer
78 views

Topological Irreducible graphs for the projective plane

I learned that there are 103 topological irreducible graphs for the projective plane but I am unable to find examples of said graphs. I am unsure of how to find them on my own and I would like to see ...
4
votes
1answer
107 views

Counting the number of $(d_v,d_c)$ regular bipartite graphs

I am trying to count the number of $(d_v,d_c)$ regular bipartite graphs. To be specific, let $n,m,d_v,d_c$ be positive integers such that $$n\times d_v=m\times d_c.$$ Then, what is the number of ...
2
votes
1answer
179 views

Coloring of subgraphs of G^n

Let $G=(L,R,E)$ be a finite bipartite graph, such that for each $v\in L\cup R: deg(v)>0$. Define $E^{(n)}=\{(\overline{l},\overline{r}) | \overline{l}=(l_1,...,l_n)\in L^n , ...
3
votes
1answer
203 views

Expected Value for a Connected Graph

Consider a connected graph of N nodes. Assign randomly to each node a distinct number from 1 to N. For each node consider the maximum adjacent value or itself if all adjacent values are smaller. ...
1
vote
0answers
126 views

A connection between nonplanar complete graphs and the alternating group?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE). I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...
2
votes
1answer
161 views

Graph of Grassmannian

Let p be an integer, and let G be the graph $(V=Gr(k,\mathbb{F}_q ^n),E)$ where: $Gr(k,\mathbb{F}_q ^n)$ is the set of all subspace of $\mathbb{F}_q$ of dimension k, and $E=\{ W_1,W_2 \in V | ...
5
votes
1answer
245 views

A new question about maximal independent sets in regular graphs

This is a question inspired by "A question about independent set in regular graphs". Suppose that $G$ is a simple $r$-regular graph with $n$ vertices. We say $H$ is a dominating set for $T$, if for ...
11
votes
2answers
360 views

Strongly connected directed graphs with large directed diameter and small undirected diameter?

This question is an attempt to make progress on domotorp's interesting challenge. This question was originally asked in two parts; the former of which was answered by Ilya Bogdanov, and the latter of ...
6
votes
0answers
135 views

Uniformly sampling from the set of all simplicial maps

Let $K$ and $L$ be finite simplicial complexes that remain fixed throughout. How does one efficiently sample (according to the uniform distribution) elements from the finite set of simplicial ...
0
votes
1answer
76 views

Basis of Cycle Subspace of a Graph

Let $G$ be a $2$-connected graph and for $e \in E(G)$ denote by $\mathcal{C_e}$ the set of all cycles(circuits) of $G$ containing the edge $e$. For what set of edges does $\mathcal{C_e}$ contain a ...
-1
votes
2answers
142 views

spanning tree of a graph of minimum degree three

Does each graph of minimum degree three admit a spanning tree whose vertices have degree three (exactly) except the leaves (degree one)?
3
votes
1answer
146 views

Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph

It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard. By Smith's theorem, ...
0
votes
1answer
217 views

A question about independent set in regular graphs

Suppose that $G$ is a simple $r$-regular graph with $n$ vertices. We say $H$ is a dominating set for $T$, if for every vertex $v\in T$, we have $v\in H$ or there is a vertex $u\in H$ such that $vu\in ...
4
votes
1answer
227 views

Fundamental Cycles of a graphs

For a $2$-edge-connected simple graph $G$ and a tree $T$ of $G$, let $C_e$ be the unique cycle in $T + e$, $e \in E(G) - E(T)$. Define the set $\mathcal{C}(T) = \{C_e | e \in E(G) - E(T)\}$. Now ...
1
vote
0answers
135 views

Can assigment of Cayley graphs be functorial?

Let $G$ and $G'$ be finitely generated groups and $f:G\to G'$ a homomorphism. First question: for a given $f:G\to G'$ it possible to select generating sets $S\in G, S'\in G'$ so that their would be a ...
2
votes
1answer
149 views

Labeling vertices in a graph

Is there an efficient algorithm for the following task?: Given a graph $G$, either find a labelling of vertices with bit strings of length $k$ such that the labels of adjacent vertices differ in ...
2
votes
2answers
213 views

Does this graph have a name?

Let $G$ be a connected graph on $n$ vertices and $\mathcal{T}$ be the set of all spanning trees of $G$. Consider the graph whose vertices are the elements of $\mathcal{T}$ and $T, T' \in ...
5
votes
1answer
180 views

Paley graphs over $p^{2}$ vertices

I have proved that every Paley graph $P(p^{2})$ over $p^{2}$ vertices, where $p\geq 5$ is a prime number has a cospectral mate, i.e. for every prime number $p\geq 5$ there exists a graph $\Gamma_{p}$ ...
7
votes
1answer
227 views

Shortest Paths in the “Cantor Graph”

First, let me explain, what I understand by a "Cantor Graph": it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of ...
2
votes
0answers
82 views

Hamiltonian Matroids

Similar to graphs, a Matroid $M$ is said to be Hamiltonian if there is a base $B$ of $M$ and $e \in M-B$ such that $B + e$ is a cycle of $M$. Is there any literature on this? EDIT: Actually my ...
7
votes
0answers
182 views

Coherence between different ranking methods of a graph's vertices

Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher. Two natural ways of doing it are: By the degrees. By the entries in a ...
0
votes
1answer
146 views

Expected length of the shortest polygonal chain connecting N random points in the unit square

N points are selected uniformly at random in the unit square. Let L(N) be the expected length of the shortest (possibly self-intersecting) polygonal chain connecting all the points. It can be proved ...
3
votes
3answers
338 views

random networks and prime numbers

I have been studying networks recently and accidentally came up with an heuristic approach towards the distribution of prime numbers. The prime number theorem states that $\pi(n)\sim n/log(n)$ for ...
5
votes
1answer
187 views

Extremal functions for tournaments

We are looking at directed graphs with no loops or parallel edges, but given two vertices $x$ and $y$, we allow the presence of both the edge $(x, y)$ and $(y, x)$. Thus, if $G$ is a directed graph ...
3
votes
1answer
178 views

Correspondence between spanning Trees and Even Subgraphs in a Graph

Let $G$ be a connected graph and $T$ a spanning tree of $G$. For $e \in E(G) - E(T)$, Let $C_{e}$ denote the unique cycle in $T + e$. Let $H(T)$ be the the subgraph of $G$ induced by symmetric ...
4
votes
2answers
123 views

Less general edge reconstruction problem for simple graphs

Let $G$ be a simple graph. Let $E^-(G)$ denote the set of (isomorphism classes) of subgraphs of $G$ that can be obtained by deleting a single edge of $G$. Similarly, let $E^+(G)$ be the set of ...
2
votes
0answers
128 views

If two graphs have same Laplacian spectrums, are they the similar graphs?

If graph A and graph B have exactly the same Laplacian spectrums, can I just say they are same graphs? (only with scaling edge weights and node index reordering) I don't know if there is any explicit ...
3
votes
1answer
204 views

Geodesic convex hulls in a graph; and their properties

This question asks for an analog of the convex hull in a graph that parallels (as far as possible) convex sets in Euclidean space. Let $G$ be a simple, undirected graph, and let $S \subseteq V$ be a ...
3
votes
0answers
68 views

Size of b-matching constructed from b maximal matchings

The Question: Let $G$ be a (simple) graph and let $b\in\mathbb{N}$. Suppose that we have $b$ disjoint edge-subsets $M_1,\ldots , M_b$ satisfying the following condition: The set $M_1$ is a maximal ...
6
votes
1answer
213 views

What is the status of this strong form of Hedetniemi's conjecture?

In this question, a graph is a finite, undirected graph without loops or multiple edges, and a colouring of a graph is a proper vertex colouring. The product $G \times H$ of graphs $G$ and $H$ is the ...
10
votes
1answer
309 views

Coloring $K_n$ via edge-weight sums

This is a question inspired by and tangential to "A Question on 1, 2 ,3 Conjecture"—and certainly much easier! Suppose one assigns a random edge weight among $\{1,2,3,\ldots,k\}$ to each edge ...
3
votes
2answers
186 views

Two graph constructions: new, old?

Let $G=(V,E)$ be a simple, undirected graph. Let $|V(G)|=n$ and $|E(G)|=m$. We consider connected graphs only. We write $i\sim j$ if $i$ and $j$ form an edge. Let $N(i)=\{j:i\sim j\}$. We write ...
16
votes
1answer
571 views

A Question on 1, 2 ,3 Conjecture

1, 2, 3 conjecture is well-known: If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the numbers ...
1
vote
1answer
103 views

Proper name for hypergrid or subdivided hypercube?

Is there a name for a graph very similar to a hypercube, but generalized from $2^d$ vertices to $k^d$? Alternatively, similar to a 2-dimensional grid, but generalized to higher dimensions? In 2 ...
0
votes
0answers
39 views

Edge versus vertex assignment in graphs and convex relaxtions

Consider a graph $G = (V,E)$. Let $x \in \{-1,1\}^V$ be a label assignment to vertices of the graph and $z \in \{-1,1\}^E$ be a label assignment to edges of the graph. We say that $z$ is compatible ...
4
votes
0answers
147 views

Unique Domino Tiling

Question: how does one enumerate all star-convex $2n$-vertex sublattices of the plane that have the unique domino-tiling property? Definitions: A subset S of the xy-plane is star-convex if there is ...
0
votes
3answers
414 views

Stationary distribution for bipartite graph

I was wondering if there is any stationary distribution for bipartite graph? Can we apply random walks on bipartite graph? since we know the stationary distribution can be found from Markov chain, but ...
4
votes
3answers
160 views

Tracking automorphism groups of graph processes

Start with an edgeless graph on $n$ labeled vertices, and note that the automorphism group is $\Sigma_n$, the symmetric group on $n$ elements. Now imagine that we randomly start throwing in all of the ...
0
votes
1answer
92 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
0
votes
0answers
65 views

Minimum cut in near complete graph

I have a problem with an algorithm that i don't quite understand. The mathematics are not the problem, but I don't understand how it can work in practice. The problem is in the paper ...
2
votes
1answer
90 views

Achieving the largest possible minimum spacing between vertices of the same color in an integer lattice

Consider an infinite integer lattice, or an infinite hexagonal lattice with unit length edges. Provided a set of $k$ possible vertex colors, is there a known largest possible minimum spacing that can ...
6
votes
2answers
389 views

Is there an algorithm to compute efficiently the dessin d'enfant from a Belyi pair?

Let $(X,f)$ be a Belyi pair, i.e. a Riemann surface $X$ together with a morphism $f: X \to \mathbb{P}^1$, ramified only in $0,1, \infty$. Grothendieck's dessin d'enfant is the pre-image $G$ of the ...
3
votes
1answer
149 views

an interesting conjecture about Hamiltonian cycle

Let G be a simple graph which is a cycle $C$ equipped with some chords such that $\delta (G)\geq 3$,in other words,every vertex of $C$ is adjacent with at least one of the chords. I conjecture that ...
0
votes
1answer
122 views

Union of perfect matchings in bridgeless cubic graphs

It's known that every cubic bridgeless graph has 1-factor (Petersen). But Does anybody know, how to prove that for every edge in a cubic bridgeless graph there exists a 1-factor, which contains it? ...
0
votes
0answers
55 views

Maximum Independent set of sparse graphs with few triangles

Notations used $\alpha(G) = $ Max sized independent set of graph $G$. $n(G) = $ Number of vertex in graph $G$. Theorem (by Ajtai et al.): For a triangle-free graph $G$ and max degree being ...
1
vote
0answers
41 views

complexity of in-dominating set

Is the decision problem In-Dominating Set NP-complete for digraphs of regular out-degree (greater than (n-2)/4, in particular)? I'm mainly looking for the reference. Thanks for any answer!
1
vote
2answers
208 views

Discrete Laplace operator and its eigenvalues

I wonder is there any geometric interpretation of the eigenvalues ​​of the discrete Laplace operator on graphs? Maybe there is a relationship between the eigenvalues ​​and combinatorial properties of ...