26-28 May 2015
Europe/Ljubljana timezone
Home > Contribution List

Contribution List

Displaying 21 contributions out of 21
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 context. We ... More
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 and t ... More
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 st ... More
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 it wa ... More
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 neig ... More
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 limi ... More
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 hypergra ... More
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 list s ... More
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 framework o ... More
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 number-theoreti ... More
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 ant ... More
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 graph. So ... More
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 posed. ... More
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.
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 called ... More
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 each g ... More
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 graphs ... More
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 \Gamma ... More
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 showing ... More
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 there i ... More
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 as ... More