Univerza na Primorskem Fakulteta za matematiko, naravoslovje in informacijske tehnologije

Raziskovalni matematični seminar - Arhiv

2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010
1 2 3 4 5 6 7 8 9 10 11 12
Datum in ura / Date and time: 12.1.15
Predavalnica / Location: FAMNIT-SEMIN
Predavatelj / Lecturer: Matjaž Krnc (Faculty of Mathematics and Physics, University of Ljubljana)
Naslov / Title: Centralization of Wiener index
Vsebina / Abstract:

Freeman's centralization for a given centrality index is a measure of how central a vertex is regarding to how central all the other vertices are with respect to the given index. The well studied Wiener index (the Wiener number) of a graph G is equal to the sum of distances between all pairs of vertices of G . In the talk I will present the centralization of Wiener index, in particular, we will determine the graphs on n vertices which attain the maximum or minimum value. 

Datum in ura / Date and time: 5.1.15
Predavalnica / Location: FAMNIT-SEMIN
Predavatelj / Lecturer: Tatiana Hartinger Romina (UP IAM)
Naslov / Title: On the structure of 1-perfectly orientable graphs
Vsebina / Abstract:

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. By definition, 1-p.o. graphs are exactly the graphs that admit an orientation that is an out-tournament. (A simple arc reversal argument shows that that 1-p.o. graphs are exactly the graphs that admit an orientation that is an in-tournament. Such orientations were called fraternal orientations in several papers.)

1-p.o. graphs form a common generalization of chordal graphs and circular arc graphs. While they can be recognized in polynomial time via a reduction to 2-SAT, little is known about their structure. We prove several results related to the structure of 1-p.o. graphs. First, we give a characterization of 1-p.o. graphs in terms of edge clique covers, similar to a known characterization of squared graphs due to Mukhopadhyay. We exhibit several examples of 1-p.o. and non-1-p.o. graphs. The examples of non-1-p.o. graphs include two infinite families: the complements of even cycles of length at least 6, and the complements of odd cycles augmented by a component consisting of a single edge. We identify several graph transformations preserving the class of 1-p.o. graphs. In particular, we show that the class of 1-p.o. graphs is closed under taking induced minors. We also study the behavior of 1-p.o. graphs under some operations that in general do not preserve the class, such as pasting along a clique and the join. The result for the join motivates the problem of characterizing the 1-p.o. co-bipartite graphs. We show that all the presented examples of non-1-p.o. graphs are minimal forbidden induced minors for the class of 1-p.o. graphs. As our main results we obtain complete characterizations of 1-p.o. graphs within the classes of complements of forests and of cographs.

Joint work with Martin Milanič.