2015 International Conference on Graph Theory

Contribution List

12. Coloring graphs without long induced paths

The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory. An especially intriguing case is that of 3-colorability. Here, the state of the art is our recent poly-time algorithm to solve the problem on graphs without induced paths on seven vertices, so-called P_7-free graphs. So far, much less was known about certification in this...

10. Counterexamples to three conjectures on equistable graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every c <= 1 and every non-empty subset T of vertices that is not a maximal stable set, there exist positive vertex weights such that every maximal stable set is of total weight 1...

15. Equistarable bipartite graphs

Recently, Milanič and Trotignon introduced the class of equistarable graphs as graphs without isolated vertices admitting positive vertex weights on the edges such that a subset of edges is of total weight 1 if and only if it forms a maximal star. Based on equistarable graphs, counterexamples to three conjectures on equistable graphs were constructed, in particular to Orlin's conjecture, which...

6. Generalized Cayley graphs

For a given group G, an automorphism \alpha of G of order two, and a subset S of G, we define a generalized Cayley graph to be the graph with the vertex set G, and the edge set { { x, \alpha(x) } | x in G }. In order to get an undirected graph without loops we add some additional constrains on the set S. Every Cayley graph is a generalized Cayley graph, but the converse is false. Recently...

9. Group labelings of graphs

In this talk we will present various kinds of graph labelings where the labels are members of Abelian groups. The talk will consist of two parts. In the first part we will present the reults on the so-called irregular labelings, i.e. such labelings of edges with elements of arbitrary Abelian groups that resulting sums at vertices are dstinct either for all the vertices of the graph or for the...

4. Improving Moore bounds via counting cycles

The Moore bound was introduced over 50 years ago as both a lower bound on the order of cages (k-regular graphs of girth g with minimal number of vertices) and an upper bound on the order of the largest graphs of maximum degree k and diameter d. Even though it is known to be sharp for both problems, the sets of parameters for which there exist graphs of orders equal to the Moore bound are very...

19. News About Efficient Domination for F-Free Graphs

For a given hypergraph H=(V,{\cal E}), the Exact Cover problem asks for the existence of a subset {\cal F} \subseteq {\cal E} of hyperedges covering every vertex of V exactly once; Exact Cover is one of Karp's famous list of 21 NP-complete problems. The NP-complete Efficient Domination (ED) problem for a graph G=(V,E) corresponds to the Exact Cover problem for the closed neighborhood...

14. On Skew-Homomorphisms

A map \phi on algebra A is called skew-morphism if there exists a function \kappa from A into integers such that \phi(ab)=\phi(a)\phi^{\kappa(a)}(b) where \phi^s is the iteration of a map \phi. Skew morphisms were recently introduced in connection to maps on orientable surfaces; they also naturally occur in investigation of cyclic extension of groups. In the proposed talk we aim to...

3. On 2-distance-balanced graphs

A graph X is said to be distance-balanced if for any edge uv of X, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. These graphs were, at least implicitly, first studied by Handa who considered distance-balanced partial cubes. The term itself, however, is due to Jerebic, Klavžar, and Rall who studied distance-balanced graphs in the...

11. On an analogue of Kummer's Theorem for the number of equipartitions

Kummer's Theorem says that the highest power of the prime p dividing the binomial coefficient n choose k is the number of carries that occur when adding the base p representations of n and n-k. We've proved an analogous characterization of the highest power of p dividing the number of partitions of [n] into d equal-sized parts. Our motivation comes from certain group-theoretic and...

16. On bipartite Q-polynomial distance-regular graphs with c_2\le 2

Let \Gamma denote a Q-polynomial bipartite distance-regular graph with diameter D, valency k \ge 3 and intersection number c_2\le 2. In this talk we show the following two results: (1) If D \ge 6, then \Gamma is either the D-dimensional hypercube, or the antipodal quotient of the 2D-dimensional hypercube. (2) If D = 4 and c_2\le 2 then \Gamma is either the 4-dimensional hypercube, or the...

5. On the eigenspaces of signed line graphs and signed subdivision graphs

In the theory of (simple) graphs the notions of line graph and subdivision graph are well-known. Recently, such graph valued functions have been considered also in the context of signed graphs, where the edges get a value in the set {1,-1} (the sign), that is the signature of the graph. Hence, we consider the following two compound graphs: the signed line graph and the signed subdivision...

8. On the structure of 1-perfectly orientable graphs

Following the terminology of Kammer and Tholey, we say that an orientation of a graph is 1-perfect if the out-neighborhood of every vertex induces a tournament, and that a graph is 1-perfectly orientable (1-p.o. for short) if it has a 1-perfect orientation. The notion of 1-p.o. graphs was introduced by Skrien (under the name B_2-graphs), where the problem of characterizing 1-p.o. graphs was...

2. Quadrangulations of polygonal regions

The talk will explain an interesting correspondence between quadrangulations of polygonal regions and graphs. This correspondence may be used for a simple coding of graphs.

17. Some applications of generalized action graphs and monodromy graphs

We define generalized action graphs as semi-directed graphs in which the edge set is partitioned into directed 2-factors (forming an action digraph) and undirected 1-factors (forming a monodromy graph) and use them to describe several combinatorial structures, such as maps and oriented maps. The quotient of the action graph with respect to its automorphism group (or some of its subgroup) is...

7. Spectral Characterization of Signed Graphs

A signed graph is pair (G,s) where G is a graph and s, the signature, is a function on the edges of G assigning values in {1,-1}. Similarly to simple unsigned graphs, it is possible to associate several graph matrices and to study the signed graphs from a spectral viewpoint. A common problem in Spectral Theory of unsigned graphs is to consider special families of graphs and to study whether...

13. The Graph Bicycle Spectrum

The cycle spectrum of a graph (the collection of all cycle lengths) has received extensive study. Since graphic matroids are based on the cycles of graphs, results in this field apply immediately to matroids. Motivated by the study of bicircular matroids, we consider the sizes of graph bicycles. That is, connected sets of edges containing exactly two cycles and no leaves. We characterize...

20. Tight distance-regular graphs with classical parameters

Let \Gamma be a distance-regular graph of diameter d. It is said to have classical parameters (d, b, \alpha, \beta) when its intersection array \{b_0,b_1,\dots,b_{d-1};c_1,c_2,\dots,c_d\} satisfies b_i = ([d] - [i])(\beta - \alpha [i]) and c_{i+1} = [i+1] (1 + \alpha [i]) (0 \le 1 \le d-1), where [j] := 1+b+\cdots+b^{j-1} is the b-analogue of j. One can say that a distance-regular graph...

1. Tri-circulant edge-transitive tetravalent graphs

This talk will outline the problem of determining all edge-transitive graphs on 3n vertices admitting a symmetry which acts on the vertices in three cycles of length n. We show the nine feasible diagrams and show how considerations of toroidal maps can give us an easy elimination of four of the nine. Two others have a more difficult elimination whose difficulties we will ignore. We end by...

21. Unit distance realizations of combinatorial zeolites

A combinatorial d-dimensional zeolite is the line graph of a (d+1)-regular graph. We show that not all combinatorial 2-d zeolites have a unit distance realization in the plane, and of those that have a unit distance realization, not all have non-overlapping unit-distance realizations. Only few classes of finite 2-d zeolites are known and a long standing conjecture of Harborth suggests that...

18. Vertex-quasiprimitivity in regular maps

A map is regular if its automorphism group acts regularly on the flag set of the map. A weaker concept is that of an orientably-regular map (on an orientable surface) in which the group of all orientation-preserving automorphisms acts regularly on the arc set of the map. We will be interested in regular and orientably-regular maps whose automorphism groups are quasiprimitive when considered...