Filters
total: 445
-
Catalog
Search results for: DIGRAPH
-
Comparison of hydrogen bonds and diverse weak interactions of the nitro group in 2-methyl-4-nitroanilinium nitrate, bisulfate and two hexafluoridosilicates: elementary graph-set approach
PublicationCrystal structures of (H2m4na)NO3 (1), (H2m4na)HSO4 (2), (H2m4na)2SiF6 (3) and (H2m4na)2SiF6*2H2O (4), where 2m4na = 2-methyl-4-nitroaniline, are presented. Two layers of interactions occur in the structures, N—H...O/F hydrogen bonds and interactions with the nitro group. Although diverse, hydrogen-bonding patterns are compared with each other by means of interrelations among elementary graph-set descriptors and descriptors of hydrogen-bonding...
-
Bond graph modeling of the new generation engine cooling systems = Zastosowanie metody grafów wiązań do modelowania nowej generacji układów chłodzenia silników spalinowych
PublicationW referacie szczegółowo opisano modele wymiany ciepła i przepływów w układzie chłodzenia. Metoda grafów wiązań okazała się szczególnie użyteczną dla modelowania skomplikowanych systemów energetycznych o różnych postaciach energii. Jako przykładu użyto obiegu chłodzenia silnika badawczego na hamowni silnikowej.
-
SIGGRAPH Asia [SA]
Conferences -
Wojciech Wojnowski dr inż.
PeopleUkończył V Liceum Ogólnokształcące w Gdańsku w klasie o profilu matematyczno-fizycznym z wykładowym językiem angielskim. W 2009 roku rozpoczął studia na Wydziale Chemicznym PG na kierunku technologia chemiczna, uzyskując w 2012 roku tytuł inżyniera, a w 2013 tytuł magistra. W latach 2013–2015 studiował sinologię na Uniwersytecie w Nankinie dzięki uzyskaniu Stypendium Rządu ChRL. Po powrocie do Polski w 2015 roku rozpoczął studia...
-
Graph Drawing
Conferences -
Dynamic Graph Workshop
Conferences -
GreedyMAX-type Algorithms for the Maximum Independent Set Problem
PublicationA maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G),...
-
ACM SIGGRAPH/Eurographics Symposium on Computer Animation
Conferences -
Topological and Geometric Graph Theory
Conferences -
Techniques and Problems in Graph Theory
Conferences -
International Conference on Graph Transformations
Conferences -
Workshop on Probabilistic Graph Theory
Conferences -
Dataset of non-isomorphic graphs of the coloring types (K4,K4;n), 1<n<R(4,4)
Open Research DataFor K4 graph, a coloring type (K4,K4;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the K4 subgraph in the second color (representing by edges in the graph).The Ramsey number R(4,4) is the smallest natural number n such that for any edge coloring of...
-
Krzysztof Goczyła prof. dr hab. inż.
PeopleKrzysztof Goczyła, full professor of Gdańsk University of Technology, computer scientist, a specialist in software engineering, knowledge engineering and databases. He graduated from the Faculty of Electronics Technical University of Gdansk in 1976 with a degree in electronic engineering, specializing in automation. Since then he has been working at Gdańsk University of Technology. In 1982 he obtained a doctorate in computer science...
-
Dataset of non-isomorphic graphs being coloring types (K5-e,Km-e;n), 2<m<5, 1<n<R(K5-e,Km-e)
Open Research DataFor K5-e and Km-e graphs, the type coloring (K5-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K5-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K5-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs being coloring types (K6-e,Km-e;n), 2<m<5, 1<n<R(K6-e,Km-e)
Open Research DataFor K6-e and Km-e graphs, the type coloring (K6-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K6-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed. The Ramsey number R(K6-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs of the coloring types (K4,Km-e;n), 2<m<5, 1<n<R(K4,Km-e)
Open Research DataFor K4 and Km-e graphs, a coloring type (K4,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4,Km-e)...
-
Conference on Graph Theory and Discrete Geometry
Conferences -
EuroConference on Combinatorics, Graph Theory and Applications
Conferences -
Workshop on Computational Graph Theory and Combinatorics
Conferences -
Workshop on Algorithms And Models For The Web Graph
Conferences -
Dataset of non-isomorphic graphs of the coloring types (Km,K3-e;n), 4<m<8, 1<n<R(Km,K3-e)
Open Research DataFor Km and K3-e graphs, a coloring type (Km,K3-e;n) is such an edge coloring of the full Kn graph, which does not have the Km subgraph in the first color (representing by no edges in the graph) or the K3-e subgraph in the second color (representing by edges in the graph). K3-e means the full Km graph with one edge removed.The Ramsey number R(Km,K3-e)...
-
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.
-
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)....
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km-e;n), 2<m<7, 1<n<R(K3,Km-e).
Open Research DataFor K3 and Km-e graphs, a coloring type (K3,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km-e subgraph in the second color (representing by edges in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3,Km-e)...
-
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...
-
Dataset of non-isomorphic graphs being coloring types (K4-e,Km-e;n), 2<m<7, 1<n<R(K4-e,Km-e)
Open Research DataFor K4-e and Km-e graphs, the type coloring (K4-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K4-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K4-e,Km-e) is the smallest...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km;n), 2<m<7, 1<n<R(3,m)
Open Research DataFor K3 and Km graphs, a coloring type (K3,Km;n) is such an edge coloring of the full Kn graph, which does not have the K3 subgraph in the first color (representing by no edges in the graph) or the Km subgraph in the second color (representing by edges in the graph).The Ramsey number R(3,m) is the smallest natural number n such that for any edge coloring...
-
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...
-
Dataset of non-isomorphic graphs being coloring types (K3-e,Km-e;n), 2<m<8, 1<n<R(K3-e,Km-e)
Open Research DataFor K3-e and Km-e graphs, the type coloring (K3-e,Km-e;n) is such an edge coloring of the full Kn graph, which does not have the K3-e subgraph in the first color (no edge in the graph) or the Km-e subgraph in the second color (exists edge in the graph). Km-e means the full Km graph with one edge removed.The Ramsey number R(K3-e,Km-e) is the smallest...
-
On trees with double domination number equal to total domination number plus one
PublicationA total dominating set of a graph G is a set D of vertices of G such that every vertex of G has a neighbor in D. A vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The total (double, respectively) domination number of a graph G is the minimum cardinality of a total (double,...
-
South African International Graph Theory Conference
Conferences -
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.
-
Interval Edge Coloring of Bipartite Graphs with Small Vertex Degrees
PublicationAn edge coloring of a graph G is called interval edge coloring if for each v ∈ V(G) the set of colors on edges incident to v forms an interval of integers. A graph G is interval colorable if there is an interval coloring of G. For an interval colorable graph G, by the interval chromatic index of G, denoted by χ'_i(G), we mean the smallest number k such that G is interval colorable with k colors. A bipartite graph G is called (α,β)-biregular...
-
A collection of directed graphs for the minimum cycle mean weight computation
Open Research DataThis dataset contains definitions of the 16 directed graphs with weighted edges that were described in the following paper: Paweł Pilarczyk, A space-efficient algorithm for computing the minimum cycle mean in a directed graph, Journal of Mathematics and Computer Science, 20 (2020), no. 4, 349--355, DOI: 10.22436/jmcs.020.04.08, URL: http://dx.doi.org/10.22436/jmcs.020.04.08 These...
-
Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
PublicationWe consider the problem of scheduling n identical jobs on 3 uniform machines with speeds s1, s2, and s3 to minimize the schedule length. We assume that jobs are subject to some kind of mutual exclusion constraints, modeled by a cubic incompatibility graph. We how that if the graph is 2-chromatic then the problem can be solved in O(n^2) time. If the graph is 3-chromatic, the problem becomes NP-hard even if s1>s2=s3.
-
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...
-
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...
-
Infinite chromatic games
PublicationIn the paper we introduce a new variant of the graph coloring game and a new graph parameter being the result of the new game. We study their properties and get some lower and upper bounds, exact values for complete multipartite graphs and optimal, often polynomial-time strategies for both players provided that the game is played on a graph with an odd number of vertices. At the end we show that both games, the new and the classic...
-
Equitable coloring of corona products of graphs
PublicationIn this paper we consider an equitable coloring of some corona products of graphs G and H in symbols, G o H). In particular, we show that deciding the colorability of G o H is NP-complete even if G is 4-regular and H is K_2. Next, we prove exact values or upper bounds on the equitable chromatic number of G o H, where G is an equitably 3- or 4-colorable graph and H is an r-partite graph, a path, a cycle or a complete graph.
-
Rendezvous of heterogeneous mobile agents in edge-weighted networks
PublicationWe introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...
-
Rendezvous of Heterogeneous Mobile Agents in Edge-Weighted Networks
PublicationWe introduce a variant of the deterministic rendezvous problem for a pair of heterogeneous agents operating in an undirected graph, which differ in the time they require to traverse particular edges of the graph. Each agent knows the complete topology of the graph and the initial positions of both agents. The agent also knows its own traversal times for all of the edges of the graph, but is unaware of the corresponding traversal...
-
Brushing with additional cleaning restrictions
PublicationIn graph cleaning problems, brushes clean a graph by traversing it subject to certain rules. We consider the process where at each time step, a vertex that has at least as many brushes as incident, contaminated edges, sends brushes down these edges to clean them. Various problems arise, such as determining the minimum number of brushes (called the brush number) that are required to clean the entire graph. Here, we study a new variant...
-
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...
-
Rendezvous of Distance-Aware Mobile Agents in Unknown Graphs
PublicationWe study the problem of rendezvous of two mobile agents starting at distinct locations in an unknown graph. The agents have distinct labels and walk in synchronous steps. However the graph is unlabelled and the agents have no means of marking the nodes of the graph and cannot communicate with or see each other until they meet at a node. When the graph is very large we want the time to rendezvous to be independent of the graph size...
-
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.
-
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...
-
On trees with double domination number equal to 2-outer-independent domination number plus one
PublicationA vertex of a graph is said to dominate itself and all of its neighbors. A double dominating set of a graph G is a set D of vertices of G such that every vertex of G is dominated by at least two vertices of D. The double domination number of a graph G is the minimum cardinality of a double dominating set of G. For a graph G=(V,E), a subset D subseteq V(G) is a 2-dominating set if every vertex of V(G)D has at least two neighbors...
-
Leader election for anonymous asynchronous agents in arbitrary networks
PublicationWe consider the problem of leader election among mobile agents operating in an arbitrary network modeled as an undirected graph. Nodes of the network are unlabeled and all agents are identical. Hence the only way to elect a leader among agents is by exploiting asymmetries in their initial positions in the graph. Agents do not know the graph or their positions in it, hence they must gain this knowledge by navigating in the graph...
-
Some variants of perfect graphs related to the matching number, the vertex cover and the weakly connected domination number
PublicationGiven two types of graph theoretical parameters ρ and σ, we say that a graph G is (σ, ρ)- perfect if σ(H) = ρ(H) for every non-trivial connected induced subgraph H of G. In this work we characterize (γw, τ )-perfect graphs, (γw, α′)-perfect graphs, and (α′, τ )-perfect graphs, where γw(G), τ (G) and α′(G) denote the weakly connected domination number, the vertex cover number and the matching number of G, respectively. Moreover,...