### ?

## Pq-König Extended Forests and Cycles

P. 86-95.

A graph is König for a q-path if every its induced subgraph has the following property. The maximum number of pairwise vertex-disjoint induced paths each on q vertices is equal to the minimum number of vertices, such that removing all the vertices produces a graph having no an induced path on q vertices. In this paper, for every q>4, we describe all Konig graphs for a q-path obtained from forests and simple sycles by replacing some vertices into graphs not containing induced paths on q vertices.

Language:
English

### In book

Vol. 1623. , CEUR Workshop Proceedings, 2016

, in: Models, Algorithms and Technologies for Network Analysis, Springer Proceedings in Mathematics & Statistics. Vol. 156.: Switzerland: Springer, 2016.. P. 45-54.

We characterize the graphs whose induced subgraphs all have the following property: The maximum number of induced 4-paths is equal to the minimum cardinality of the set of vertices such that every induced 4-path contains at least one of them. In this chapter we describe all such graphs obtained from simple cycles by replacing some ...

Added: October 24, 2016

European Journal of Combinatorics 2012 Vol. 33 No. 4 P. 534-543

For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...

Added: June 28, 2012

Дискретный анализ и исследование операций 2012 Т. 19 № 6 С. 37-48

Понятие граничного класса графов является полезным инструментом для анализа вычислительной сложности задач на графах в семействе наследственных классов. В предыдущих работах автора исследовались общие черты и особенности семейств граничных классов графов для задачи о вершинной k-раскраске и ее «предельного варианта» - задачи о хроматическом числе. В данной работе эта проблематика рассматривается применительно к реберному варианту ...

Added: November 30, 2012

Siberian Electronic Mathematical Reports 2014 Vol. 11 P. 811-822

We obtain a complete complexity dichotomy for the edge 3- colorability within the family of hereditary classes defined by forbidden
induced subgraphs on at most 6 vertices and having at most two 6-vertex forbidden induced structures. ...

Added: April 7, 2014

Известия высших учебных заведений. Математика 2016 Т. 6 С. 63-74

As a solution concept of cooperative TU-game we propose the set of $\alpha$-prenucleoli, $\alpha\in R$, that is a generalization of the $[0,1]$-prenucleolus. In the paper we show that in a cooperative game the set of $\alpha$-prenucleoli takes into account the constructive power with weight $\alpha$ and the blocking power with weight $(1-\alpha)$ for all possible ...

Added: October 20, 2015

Electronic Journal of Combinatorics 2011 Vol. 18 No. 1 P. 1-14

For a graph property X, let Xn be the number of graphs with vertex set {1, . . . , n} having property X, also known as the speed of X. A property X is called factorial if X is hereditary (i.e. closed under taking induced subgraphs) and nc1n ≤ Xn ≤ nc2n for some ...

Added: June 28, 2012

Theoretical Computer Science 2011 No. 412 P. 3545-3554

The notion of a boundary graph property was recently introduced as a relaxation of that of a minimal property and was applied to several problems of both algorithmic and combinatorial nature. In the present paper, we first survey recent results related to this notion and then apply it to two algorithmic graph problems: Hamiltonian cycle ...

Added: September 11, 2012

Дискретный анализ и исследование операций 2013 Т. 20 № 6 С. 30-39

For a set of labeled graphs X, let Xn be the set of n-vertex graphs from X. Hereditary class X is called at most factorial if there exist positive constants c,n0 such that |Xn| < n^{cn} for all n > n0. Lozin's conjecture states that hereditary class X is at most factorial if and only ...

Added: November 18, 2013

Discrete Mathematics 2015 Vol. 338 No. 2 P. 164-179

The idea of implicit representation of graphs was introduced in Kannan et al. (1992) and can be defined as follows. A representation of an n-vertex graph G is said to be implicit if it assigns to each vertex of G a binary code of length O(logn) so that the adjacency of two vertices is a function of their codes. Since an implicit ...

Added: March 16, 2015

Revue des etudes slaves 2016 Vol. 87 No. 1 P. 35-51

The article is devoted to the main theoretical ideas of Russian classicist Olga M. Feidenberg (1890-1955). During her lifetime under a press of Stalinist persecutions and defamation she had published a meager part of her works. And because of association with N.Marr, with whom she collaborated at the early stage of her career, her written ...

Added: October 13, 2017

Montenegrin Journal of Economics 2013 Vol. 9 No. 3 P. 7-27

A new approach is proposed revealing duality relations between a physical side of economy (resources and technologies) and its institutional side (institutional relationsd between social groups). Production function is modeled not as a primal object but rather as a secondary one defined in a dual way by the institutional side. Differential games of bargaining are ...

Added: November 1, 2013

Journal of Applied and Industrial Mathematics 2017 Vol. 11 No. 1 P. 99-106

The notions of boundary and minimal hard classes of graphs, united by the term “critical classes”, are useful tools for analysis of computational complexity of graph problems in the family of hereditary graph classes. In this family, boundary classes are known for several graph problems. In the paper, we consider critical graph classes in the ...

Added: February 13, 2017

A complexity dichotomy for the dominating set problem / Cornell University. Series "Working papers by Cornell University". 2015.

We completely determine the complexity status of the dominating set problem for hereditary graph classes defined by forbidden
induced subgraphs with at most five vertices. ...

Added: June 2, 2015

Discrete Applied Mathematics 2017 Vol. 219 P. 158-166

We show that the chromatic number of {P_5,K_p-e}-free graphs can be computed in polynomial time for each fixed p.
Additionally, we prove polynomial-time solvability of the weighted vertex coloring problem for {P_5,co(P_3+P_2)}-free graphs. ...

Added: November 21, 2016

, in: Rendiconti per gli Studi Economici quantitativi 2000. .: Venice: Università Ca’Foscari di Venezia, Dipartimento di Matematica Applicata, 2001.. P. 25-39 .

We consider a monopolistic firm that sells seasonal goods. The firm seeks the minimum of the total advertising expenditure during the selling period, given that some previously defined levels of goodwill and sales have to be reached at the end of the period. The only control allowed is on advertising while goodwill and sales levels ...

Added: November 19, 2013

, in: Contributions to game theory and management. Issue 6.: St. Petersburg: Graduate School of Management, St. Petersburg University, 2013.. P. 289-300.

In the present paper the game theory is applied to an important open question in economics: providing microfoundations for often-used types of production function. Simple differential games of bargaining are proposed to model a behavior of workers and capital-owners in processes of formation of a set of admissible factor prices or participants’ weights (moral-ethical assessments). ...

Added: November 6, 2013

Optimization Letters 2016 Vol. 10 No. 8 P. 1593-1612

The task of complete complexity dichotomy is to clearly distinguish between easy and hard cases of a given problem on a family of subproblems. We consider this task for some optimization problems restricted to certain classes of graphs closed under deletion of vertices. A concept in the solution process is based on revealing the so-called ...

Added: December 18, 2015

Вопросы литературы 2016 № 5 С. 176-190

Human nature’s complexity and contradictoriness, accentuating the enigmatic essence of the Russian mentality, receives a unique depiction in Dostoevsky’s works. Often we read about strange specimens, whose thoughts and actions would bear typical features of Russian culture. The article sets out to examine these features: in particular, duality and a combination of mutually excluding qualities. ...

Added: December 16, 2016

Russian Mathematics 2016 Vol. 60 No. 6 P. 63-74

We understand a solution of a cooperative TU-game as the α-prenucleoli set, α ∈ R, which is a generalization of the notion of the [0, 1]-prenucleolus. We show that the set of all α-nucleoli takes into account the constructive power with the weight α and the blocking power with the weight (1 − α) for all possible values of the parameter α. The ...

Added: July 7, 2016

Communications in Mathematical Physics 2019 No. 367 P. 455-481

On a Fock space constructed from mn free bosons and lattice Z mn , we give a level n action of the quantum toroidal algebra E m associated to gl m , together with a level m action of the quantum toroidal algebra E n associated to gl n . We prove that the E ...

Added: December 10, 2019

Discrete Applied Mathematics 2018 Vol. 247 P. 423-432

We show that the weighted coloring problem can be solved for {P5,banner}-free graphs and for {P5,dart}-free graphs in polynomial time on the sum of vertex weights. ...

Added: April 23, 2018

Duality of critical interfaces in Potts model: numerical check / Cornell University. Series "Working papers by Cornell University". 2010. No. 1008.3573.

We report on numerical investigation of fractal properties of critical interfaces in two-dimensional Potts models. Algorithms for finding percolating interfaces of Fortuin-Kasteleyn clusters, their external perimeters and interfaces of spin clusters are presented. Fractal dimensions are measured and compared to exact theoretical predictions. ...

Added: March 7, 2016

Дискретная математика 2012 Т. 24 № 2 С. 75-78

В данной работе исследуются семейства граничных классов для задач о вершинной k-раскраске и о хроматическом числе. Указано континуальное семейство классов графов, являющихся граничными одновременно для первой задачи при k=3 и для второй. Для любого k>3 выявлено континуальное семейство граничных классов для первой задачи, не являющихся граничными для второй. Для задачи о хроматическом числе найден граничный ...

Added: November 30, 2012