Search
Filters
total: 5311
filtered: 4737
-
Catalog
Chosen catalog filters
displaying 1000 best results Help
Search results for: PERFECT GRAPHS
-
Interval incidence coloring of bipartite graphs
PublicationIn this paper we study the problem of interval incidence coloring of bipartite graphs. We show the upper bound for interval incidence coloring number (χii) for bipartite graphs χii≤2Δ, and we prove that χii=2Δ holds for regular bipartite graphs. We solve this problem for subcubic bipartite graphs, i.e. we fully characterize the subcubic graphs that admit 4, 5 or 6 coloring, and we construct a linear time exact algorithm for subcubic...
-
Distributed Evacuation in Graphs with Multiple Exits
PublicationWe consider the problem of efficient evacuation using multiple exits. We formulate this problem as a discrete problem on graphs where mobile agents located in distinct nodes of a given graph must quickly reach one of multiple possible exit nodes, while avoiding congestion and bottlenecks. Each node of the graph has the capacity of holding at most one agent at each time step. Thus, the agents must choose their movements strategy...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublicationIn this paper we consider a problem of graph P-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs P. We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a P-coloring with a least k colors is NP-complete for an infinite...
-
Equitable coloring of corona multiproducts of graphs
PublicationWe give some results regarding the equitable chromatic number for l-corona product of two graphs: G and H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a cycle or a complete graph. Our proofs lead to polynomial algorithms for equitable coloring of such graph products provided that there is given an equitable coloring of G.
-
Computational aspects of greedy partitioning of graphs
PublicationIn this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy...
-
A Framework for Searching in Graphs in the Presence of Errors
PublicationWe consider a problem of searching for an unknown target vertex t in a (possibly edge-weighted) graph. Each vertex-query points to a vertex v and the response either admits that v is the target or provides any neighbor s of v that lies on a shortest path from v to t. This model has been introduced for trees by Onak and Parys [FOCS 2006] and for general graphs by Emamjomeh-Zadeh et al. [STOC 2016]. In the latter, the authors provide...
-
On Symmetry of Uniform and Preferential Attachment Graphs
PublicationMotivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number m of existing ones according to some attachment scheme. We prove symmetry results for m=1 and 2 , and we conjecture that for m≥3 , both models yield asymmetry with high...
-
On domination multisubdivision number of unicyclic graphs
PublicationThe paper continues the interesting study of the domination subdivision number and the domination multisubdivision number. On the basis of the constructive characterization of the trees with the domination subdivision number equal to 3 given in [H. Aram, S.M. Sheikholeslami, O. Favaron, Domination subdivision number of trees, Discrete Math. 309 (2009), 622–628], we constructively characterize all connected unicyclic graphs with...
-
Interval incidence coloring of subcubic graphs
PublicationIn this paper we study the problem of interval incidence coloring of subcubic graphs. In [14] the authors proved that the interval incidence 4-coloring problem is polynomially solvable and the interval incidence 5-coloring problem is N P-complete, and they asked if χii(G) ≤ 2∆(G) holds for an arbitrary graph G. In this paper, we prove that an interval incidence 6-coloring always exists for any subcubic graph G with ∆(G) = 3.
-
Dynamic F-free Coloring of Graphs
PublicationA problem of graph F-free coloring consists in partitioning the vertex set of a graph such that none of the resulting sets induces a graph containing a fixed graph F as an induced subgraph. In this paper we consider dynamic F-free coloring in which, similarly as in online coloring, the graph to be colored is not known in advance; it is gradually revealed to the coloring algorithm that has to color each vertex upon request as well...
-
Colorings of the Strong Product of Circulant Graphs
PublicationGraph coloring is one of the famous problems in graph theory and it has many applications to information theory. In the paper we present colorings of the strong product of several circulant graphs.
-
On the metric dimension of corona product graphs
PublicationWe give several results on the metric dimension of corona product graphs.
-
The hat problem on a union of disjoint graphs
PublicationThe topic is the hat problem in which each of n players is randomly fitted with a blue or red hat. Then everybody can try to guess simultaneously his own hat color by looking at the hat colors of the other players. The team wins if at least one player guesses his hat color correctly, and no one guesses his hat color wrong; otherwise the team loses. The aim is to maximize the probability of winning. In this version every player...
-
Non-isolating 2-bondage in graphs
PublicationA 2-dominating set of a graph G=(V,E) is a set D of vertices of G such that every vertex of V(G)D has at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. The non-isolating 2-bondage number of G, denoted by b_2'(G), is the minimum cardinality among all sets of edges E' subseteq E such that delta(G-E') >= 1 and gamma_2(G-E') > gamma_2(G)....
-
On the hardness of computing span of subcubic graphs
PublicationIn the paper we study the problem of finding ξ-colorings with minimal span, i.e. the difference between the largest and the smallest color used.
-
Weakly connected Roman domination in graphs
PublicationA Roman dominating function on a graph G=(V,E) is defined to be a function f :V → {0,1,2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v)=2. A dominating set D⊆V is a weakly connected dominating set of G if the graph (V,E∩(D×V)) is connected. We define a weakly connected Roman dominating function on a graph G to be a Roman dominating function such that the set...
-
On proper (1,2)‐dominating sets in graphs
PublicationIn 2008, Hedetniemi et al. introduced the concept of (1,)-domination and obtained some interesting results for (1,2) -domination. Obviously every (1,1) -dominating set of a graph (known as 2-dominating set) is (1,2) -dominating; to distinguish these concepts, we define a proper (1,2) -dominating set of a graph as follows: a subset is a proper (1,2) -dominating set of a graph if is (1,2) -dominating and it is not a (1,1) -dominating...
-
Mobile mutual-visibility sets in graphs
PublicationGiven a connected graph G, the mutual-visibility number of G is the cardinality of a largest set S such that for every pair of vertices x, y ∈ S there exists a shortest x, y-path whose interior vertices are not contained in S. Assume that a robot is assigned to each vertex of the set S. At each stage, one robot can move to a neighbouring vertex. Then S is a mobile mutual-visibility set of G if there exists a sequence of moves of...
-
Strong weakly connected domination subdivisible graphs
PublicationArtykuł dotyczy wpływu podziału krawędzi na liczbę dominowania słabo spójnego. Charakteryzujemy grafy dla których podział dowolnej krawędzi zmienia liczbę dominowania słabo spójnego oraz grafy dla których podział dowolnych dwóch krawędzi powoduje zmianę liczby dominowania słabo spójnego.
-
On extremal sizes of locally k-tree graphs
PublicationA graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k>=0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k >= 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the...
-
Sum Coloring of Bipartite Graphs with Bounded Degree
Publication -
program verification strategy and edge ranking of graphs
PublicationW artykule rozważamy model, w którym zakładamy, że dany jest zbiór asercji/testów dla pewnych bloków programu. Celem jest znalezienie optymalnej, tzn. wymagającej wykonania minimalnej liczby testów strategii wyszukiwania błędu w kodzie programu. Pomimo założenia w modelu, iż program posiada dokładnie jeden błąd, rozważania można uogólnić na testowanie kodu z dowolną liczbą błędów. Analizujemy teoretyczne własności tego modelu oraz...
-
On the size of identifying codes in triangle-free graphs
PublicationIn an undirected graph G, a subset C⊆V(G) such that C is a dominating set of G, and each vertex in V(G) is dominated by a distinct subset of vertices from C, is called an identifying code of G. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph G, let gammaID(G) be the minimum cardinality of an identifying code in G. In this paper, we show that for any connected...
-
Domination-Related Parameters in Rooted Product Graphs
PublicationAbstract A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those sets of vertices of a graph satisfying some domination property together with other conditions on the vertices of G. Here, we investigate several domination-related parameters in rooted product graphs.
-
On bipartization of cubic graphs by removal of an independent set
PublicationWe study a new problem for cubic graphs: bipartization of a cubic graph Q by deleting sufficiently large independent set.
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublicationA team of mobile agents starting from homebases need to visit and clean all nodes of the network. The goal is to find a strategy, which would be optimal in the sense of the number of needed entities, the number of moves performed by them or the completion time of the strategy. Currently, the field of distributed graph searching by a team of mobile agents is rapidly expanding and many new approaches and models are being presented...
-
Towards Increasing Density of Relations in Category Graphs
PublicationIn the chapter we propose methods for identifying new associations between Wikipedia categories. The first method is based on Bag-of-Words (BOW) representation of Wikipedia articles. Using similarity of the articles belonging to different categories allows to calculate the information about categories similarity. The second method is based on average scores given to categories while categorizing documents by our dedicated score-based...
-
Bipartite theory of graphs: outer-independent domination
PublicationLet $G = (V,E)$ be a bipartite graph with partite sets $X$ and $Y$. Two vertices of $X$ are $X$-adjacent if they have a common neighbor in $Y$, and they are $X$-independent otherwise. A subset $D \subseteq X$ is an $X$-outer-independent dominating set of $G$ if every vertex of $X \setminus D$ has an $X$-neighbor in $D$, and all vertices of $X \setminus D$ are pairwise $X$-independent. The $X$-outer-independent domination number...
-
Minimum order of graphs with given coloring parameters
PublicationA complete k-coloring of a graph G=(V,E) is an assignment F: V -> {1,...,k} of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number χ(G) and achromatic number ψ(G), respectively),...
-
Total Domination Versus Domination in Cubic Graphs
PublicationA dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number,γ(G), and total domination number, γ_t(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, \Gamma(G), and the upper total domination...
-
Synchronous black hole search in directed graphs
PublicationThe paper considers a team of robots which has to explore a graph G, where some nodes can be harmful. Robots are initially located at the so-called home base node. The dangerous nodes are the so-called black hole nodes, and once a robot enters in one of them, it is destroyed. The goal is to find a strategy in order to explore G in such a way that minimum number of robots is wasted. The exploration ends if there is at least one...
-
Parallel query processing and edge ranking of graphs
PublicationArtykuł poświęcony jest problemowi szukania drzewa spinającego o minimalnym uporządkowanym indeksie chromatycznym. Jednym z zastosowań jest poszukiwanie optymalnych harmonogramów w równoległym przetwarzaniu zapytań w relacyjnych bazach danych. Podajemy nowe oszacowanie funkcji dobroci przybliżonego algorytmu autorstwa Makino, Uno i Ibaraki wraz z rezultatami testów komputerowych przeprowadzonych dla grafów losowych.
-
Edge and Pair Queries-Random Graphs and Complexity
PublicationWe investigate two types of query games played on a graph, pair queries and edge queries. We concentrate on investigating the two associated graph parameters for binomial random graphs, and showing that determining any of the two parameters is NP-hard for bounded degree graphs.
-
Chromatic cost coloring of weighted bipartite graphs
PublicationGiven a graph G and a sequence of color costs C, the Cost Coloring optimization problem consists in finding a coloring of G with the smallest total cost with respect to C. We present an analysis of this problem with respect to weighted bipartite graphs. We specify for which finite sequences of color costs the problem is NP-hard and we present an exact polynomial algorithm for the other finite sequences. These results are then extended...
-
On the super domination number of lexicographic product graphs
PublicationThe neighbourhood of a vertexvof a graphGis the setN(v) of all verticesadjacent tovinG. ForD⊆V(G) we defineD=V(G)\D. A setD⊆V(G) is called a super dominating set if for every vertexu∈D, there existsv∈Dsuch thatN(v)∩D={u}. The super domination number ofGis theminimum cardinality among all super dominating sets inG. In this article weobtain closed formulas and tight bounds for the super dominating number oflexicographic product...
-
Graphs with equal domination and certified domination numbers
PublicationA setDof vertices of a graphG= (VG,EG) is a dominating set ofGif every vertexinVG−Dis adjacent to at least one vertex inD. The domination number (upper dominationnumber, respectively) ofG, denoted byγ(G) (Γ(G), respectively), is the cardinality ofa smallest (largest minimal, respectively) dominating set ofG. A subsetD⊆VGis calleda certified dominating set ofGifDis a dominating set ofGand every vertex inDhas eitherzero...
-
Domination subdivision and domination multisubdivision numbers of graphs
PublicationThe domination subdivision number sd(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number of G. It has been shown [10] that sd(T)<=3 for any tree T. We prove that the decision problem of the domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the domination multisubdivision number...
-
Graphs hard-to-process for greedy algorithm MIN
PublicationWe compare results of selected algorithms that approximate the independence number in terms of the quality of constructed solutions. Furthermore, we establish smallest hard- to-process graphs for the greedy algorithm MIN.
-
Paired domination subdivision and multisubdivision numbers of graphs
PublicationThe paired domination subdivision number sdpr(G) of a graph G is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the paired domination number of G. We prove that the decision problem of the paired domination subdivision number is NP-complete even for bipartite graphs. For this reason we define the paired domination muttisubdivision number of a nonempty graph...
-
Progress on Roman and Weakly Connected Roman Graphs
PublicationA graph G for which γR(G)=2γ(G) is the Roman graph, and if γwcR(G)=2γwc(G), then G is the weakly connected Roman graph. In this paper, we show that the decision problem of whether a bipartite graph is Roman is a co-NP-hard problem. Next, we prove similar results for weakly connected Roman graphs. We also study Roman trees improving the result of M.A. Henning’s A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002)....
-
Sum coloring of bipartite graphs with bounded degree.
PublicationArtykuł poświęcony jest złożoności obliczeniowej zagadnienia sumacyjnego kolorowania grafów dwudzielnych o ograniczonym stopniu. Zawiera dowód tego, że sumacyjne kolorowanie grafów dwudzielnych stopnia mniejszego równego 5 jest NP-zupełne oraz opis wielomianowego algorytmu, który optymalnie sumacyjnie koloruje grafy dwudzielne podkubiczne.
-
Cholesky factorization of matrices in parallel and ranking of graphs.
PublicationUporządkowane kolorowanie znajduje zastosowanie przy równoległej faktoryzacji macierzy metodą Cholesky'ego. Praca zawiera opis tego zastosowania. Podano także algorytmy optymalnego uporządkowanego kolorowania krawędzi pewnych klas grafów: grafów pełnych dwudzielnych oraz powstałych z pełnych dwudzielnych przez usunięcie O(log n) krawędzi.
-
Critical graphs upon multiple edge subdivision
PublicationA subset D of V (G) is a dominating set of a graph G if every vertex of V (G) − D has at least one neighbour in D; let the domination number γ(G) be the minimum cardinality among all dominating sets in G. We say that a graph G is γ-q-critical if subdividing any q edges results in a graph with domination number greater than γ(G) and there exists a set of q − 1 edges such that subdividing these edges results in a graph with domination...
-
Self-stabilizing algorithm for edge-coloring of graphs
PublicationReferat ten poświęcony jest kolorowaniu grafów w modelu rozproszonym.Podano samostabilizujący się algorytm kolorowania krawędzi grafu wraz z dowodem poprawności oraz oszacowaniem jego czasu działania.
-
Graphs with convex domination number close to their order
PublicationW pracy opisane są grafy z liczbą dominowania wypukłego bliską ilości ich wierzchołków.
-
Effect of grain preservation on the carotenoid and tocopherol content of cereal grains
Publication -
EvOLAP Graph – Evolution and OLAP-Aware Graph Data Model
PublicationThe objective of this paper is to propose a graph model that would be suitable for providing OLAP features on graph databases. The included features allow for a multidimensional and multilevel view on data and support analytical queries on operational and historical graph data. In contrast to many existing approaches tailored for static graphs, the paper addresses the issue for the changing graph schema. The model, named Evolution...
-
Improvement of Imperfect String Matching Based on Asymetric n-Grams
PublicationTypical approaches to string comparing treats them as either different or identical without taking into account the possibility of misspelling of the word. In this article we present an approach we used for improvement of imperfect string matching that allows one to reconstruct potential string distortions. The proposed method increases the quality of imperfect string matching, allowing the lookup of misspelled words without significant...
-
The maximum edge-disjoint paths problem in complete graphs
PublicationRozważono problem ścieżek krawędziowo rozłącznych w grafach pełnych. Zaproponowano wielomianowe algorytmy: 3.75-przybliżony (off-line) oraz 6.47-przybliżony (on-line), poprawiając tym samym wyniki wcześniej znane z literatury [P. Carmi, T. Erlebach, Y. Okamoto, Greedy edge-disjoint paths in complete graphs, in: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, in: LNCS, vol. 2880, 2003, pp. 143-155]. Ponadto...
-
Graphs with equal domination and 2-distance domination numbers
PublicationW publikacji scharakteryzowane są wszystkie te drzewa i grafy jednocykliczne, w których liczba dominowania oraz liczba 2-dominowania na odległość są sobie równe.