Filtry
wszystkich: 583
-
Katalog
Wyniki wyszukiwania dla: GRAPH THEORY · DOMINATION · PAIRED DOMINATION · TOTAL DOMINATION · PACKING NUMBER
-
Communications in Number Theory and Physics
Czasopisma -
International Journal of Number Theory
Czasopisma -
The share of BEV and PHEV in total number of registered vehicles (%) 2011-2016
Dane BadawczeIn 2016, the highest percentage of electric vehicles among all passenger automobiles was recorded in Norway - about 28% (it should be noted that in 5 years the number of electric cars in this country increased from 5 thousand to 133 thousand). However, the remaining countries in the ranking note a much smaller share of sales of electric vehicles in...
-
Some variations of perfect graphs
PublikacjaWe consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing...
-
Determination of the total number of microorganisms in a model food product preserved by CS-2a and CS-2b.
Dane BadawczeThe dataset contains the results of determination of the total number of microorganisms in a model food product after the use of the innovative preservatives: CS-2a and CS-2b and control (K) after seven days of refrigerated storage of the product. The test was performed using the surface inoculation method.
-
Electronic Journal of Graph Theory and Applications
Czasopisma -
Notes on Number Theory and Discrete Mathematics
Czasopisma -
Moscow Journal of Combinatorics and Number Theory
Czasopisma -
Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions
Publikacja -
Microbiological Survey in Two Arctic Fjords: Total Bacterial Number and Biomass Comparison of Hornsund and Kongsfjorden
Publikacja -
International Journal of Combinatorial Graph Theory and Applications
Czasopisma -
Kacper Wereszko mgr inż.
OsobyKacper Wereszko uzyskał tytuł zawodowy magistra inżyniera w 2016 roku (kierunek: informatyka, specjalność: algorytmy i technologie internetowe), a od 2017 roku jest uczestnikiem studiów doktoranckich z dyscypliny Informatyka. Obecnie pracuje jako asystent w Katedrze Algorytmów i Modelowania Systemów. Jego zainteresowania badawcze obejmują badanie własności bezpieczeństwa w grafach, problemy dominowania w grafach oraz ich praktyczne...
-
Super Dominating Sets in Graphs
PublikacjaIn this paper some results on the super domination number are obtained. We prove that if T is a tree with at least three vertices, then n2≤γsp(T)≤n−s, where s is the number of support vertices in T and we characterize the extremal trees.
-
JP Journal of Algebra Number Theory and Applications
Czasopisma -
Paweł Możejko dr hab.
Osoby -
JOURNAL OF GRAPH THEORY
Czasopisma -
Valence state of Manganium in a MnCoO ceramics
Dane BadawczeManganium -cobalt based ceramics materials were produced by solid state reaction and sintred in a furnance in air atmosphere for 20h. Annealing temperature was 600 Celsius degree. For investigations a series of samples, with a various composition was chosen: MnCoO, Mn, Co2O and Mn2CoO. In order to determine valence states of the Mn, X-Ray photoemission...
-
Equitable coloring of corona multiproducts of graphs
PublikacjaWe 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.
-
The Potential of Greed for Independence
PublikacjaThe well-known lower bound on the independence number of a graph due to Caro and Wei can be established as a performance guarantee of two natural and simple greedy algorithms or of a simple randomized algorithm. We study possible generalizations and improvements of these approaches using vertex weights and discuss conditions on so-called potential functions p(G) : V(G) -> N_0 defined on the vertex set of a graph G for which suitably...
-
Marek Kubale prof. dr hab. inż.
OsobyDetails concerning: Qualifications, Experiences, Editorial boards, Ph.D. theses supervised, Books, and Recent articles can be found at http://eti.pg.edu.pl/katedra-algorytmow-i-modelowania-systemow/Marek_KubaleGoogle ScholarSylwetka prof. Marka Kubalego Prof. Marek Kubale pracuje na Wydziale ETI Politechniki Gdańskiej nieprzerwanie od roku 1969. W tym czasie napisał ponad 150 prac naukowych, w tym ponad 40 z listy JCR. Ponadto...
-
Parity vertex colouring of graphs
PublikacjaA parity path in a vertex colouring of a graph is a path along which each colour is used an even number of times. Let Xp(G) be the least number of colours in a proper vertex colouring of G having no parity path. It is proved that for any graph G we have the following tight bounds X(G) <= Xp(G) <=|V(G)|− a(G)+1, where X(G) and a(G) are the chromatic number and the independence number of G, respectively. The bounds are improved for...
-
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublikacjaIn the paper, we show that the incidence chromatic number of a complete k-partite graph is at most ∆+2 (i.e., proving the incidence coloring conjecture for these graphs) and it is equal to ∆+1 if and only if the smallest part has only one vertex.
-
Graph classes generated by Mycielskians
PublikacjaIn this paper we use the classical notion of weak Mycielskian M'(G) of a graph G and the following sequence: M'_{0}(G) =G, M'_{1}(G)=M'(G), and M'_{n}(G)=M'(M'_{n−1}(G)), to show that if G is a complete graph oforder p, then the above sequence is a generator of the class of p-colorable graphs. Similarly, using Mycielskian M(G) we show that analogously defined sequence is a generator of the class consisting of graphs for which the...
-
T-colorings, divisibility and circular chromatic number
PublikacjaLet T be a T-set, i.e., a finite set of nonnegative integers satisfying 0 ∈ T, and G be a graph. In the paper we study relations between the T-edge spans espT (G) and espd⊙T (G), where d is a positive integer and d ⊙ T = {0 ≤ t ≤ d (max T + 1): d |t ⇒ t/d ∈ T} . We show that espd⊙T (G) = d espT (G) − r, where r, 0 ≤ r ≤ d − 1, is an integer that depends on T and G. Next we focus on the case T = {0} and show that espd⊙{0} (G) =...
-
Optimal backbone coloring of split graphs with matching backbones
PublikacjaFor a graph G with a given subgraph H, the backbone coloring is defined as the mapping c: V(G) -> N+ such that |c(u)-c(v)| >= 2 for each edge uv \in E(H) and |c(u)-c(v)| >= 1 for each edge uv \in E(G). The backbone chromatic number BBC(G;H) is the smallest integer k such that there exists a backbone coloring with max c(V(G)) = k. In this paper, we present the algorithm for the backbone coloring of split graphs with matching backbone.
-
Public spaces connecting cities. Green and Blue Infrastructures potential.
PublikacjaA city fragmentation causes a lot of negative effects in urban environment such as: disconnecting the environmental, functional and compositional relations, a loss of urban compactness, chaotic development, visual chaos, a domination of technical landscape, reduction of security. This is why one of main challenges for urban planners is to connect the fragmented structures by creating friendly, attractive and safe public space....
-
Some Progress on Total Bondage in Graphs
PublikacjaThe total bondage number b_t(G) of a graph G with no isolated vertex is the cardinality of a smallest set of edges E'⊆E(G) for which (1) G−E' has no isolated vertex, and (2) γ_t(G−E')>γ_t(G). We improve some results on the total bondage number of a graph and give a constructive characterization of a certain class of trees achieving the upper bound on the total bondage number.
-
Pressure drop and heat transfer during boiling and condensation at subcritical region
PublikacjaMost of the data presented in the literature relate to saturation temperatures in the range - 20°C to 40°C due to the application in refrigeration technology. There is necessity to extend databases to higher values of saturation temperature due to new applications such as Organic Rankine Cycle and high temperature heat pumps. Only few papers contain data for high reduced pressure for low boiling point liquids. This paper focus...
-
Total chromatic sum for trees
PublikacjaThe total chromatic sum of a graph is the minimum sum of colors (natural numbers) taken over all proper colorings of vertices and edges of a graph. We provide infinite families of trees for which the minimum number of colors to achieve the total chromatic sum is equal to the total chromatic number. We construct infinite families of trees for which these numbers are not equal, disproving the conjecture from 2012.
-
Numerical modeling of exciton impact in two crystalographic phases of the organo-lead halide perovskite (CH3NH3PbI3) solar cell
PublikacjaTo improve the power conversion efficiency of solar cells based on organo–lead halide perovskites, a detailed understanding of the device physics is fundamental. Here, a computational analysis of excitons impact is reported for these types of photocell. Numerical calculations based on the model, which take into account electronic charge carriers (electrons and holes), excitons and ions, have been carried out. The role of excitons...
-
Topological and Geometric Graph Theory
Konferencje -
Techniques and Problems in Graph Theory
Konferencje -
Workshop on Probabilistic Graph Theory
Konferencje -
Activation of peroxymonosulfate using carbon black nano-spheres/calcium alginate hydrogel matrix for degradation of acetaminophen: Fe3O4 co-immobilization and microbial community response
PublikacjaHerein, we focused on the degradation of acetaminophen (ACT) drug in liquid phase by peroxymonosulfate (PMS) activated by carbon black nano-spheres (CBNS). The nanostructured activator was immobilized into calcium alginate hydrogel matrix (CAHM) to avoid the washout of the fine nanostructures. The Langmuir modeling showed an insignificant contribution to the adsorption process in the removal of ACT. The basic pH conditions favored...
-
Current status and future success of renewable energy in Pakistan
PublikacjaMismatch between energy demand and supply from last two decades has been increasing because of the domination of expensive imported oil in energy mix of Pakistan. To import crude oil Government paid US $ 9 billion in 2008–2009 to meet the energy demands...
-
Conference on Graph Theory and Discrete Geometry
Konferencje -
EuroConference on Combinatorics, Graph Theory and Applications
Konferencje -
Workshop on Computational Graph Theory and Combinatorics
Konferencje -
A note on total reinforcement in graphs
PublikacjaIn this note we prove a conjecture and inprove some results presendet in a recent paper of N. Sridharan, M.D. Elias, V.S.A. Subramanian, Total reinforcement number of a graph, AKCE Int. J. Graphs Comb. 4 (2) (2007) 197-202.
-
Unexpected Z/E isomerism of N-methyl-O-phosphothioyl benzohydroxamic acids, their oxyphilic reactivity and inertness to amines
PublikacjaThiophosphinoylation of N-methyl p-substituted benzohydroxamic acids using disulfanes (method A) or diphenylphosphinothioyl chloride (method B) provides only one conformer of the respective O-phosphothioyl derivative (Xray and NMR analysis). Undergoing the P-transamidoxylation reaction is an evidence of the reversibility of thiophosphinoylation. Only those products containing strong EWG substituents in the aroyl residue or bulky...
-
Colorings of the Strong Product of Circulant Graphs
PublikacjaGraph 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.
-
Scheduling of identical jobs with bipartite incompatibility graphs on uniform machines. Computational experiments
PublikacjaWe consider the problem of scheduling unit-length jobs on three or four uniform parallel machines to minimize the schedule length or total completion time. We assume that the jobs are subject to some types of mutual exclusion constraints, modeled by a bipartite graph of a bounded degree. The edges of the graph correspond to the pairs of jobs that cannot be processed on the same machine. Although the problem is generally NP-hard,...
-
Mutual Interaction between Temperature and DO Set Point on AOB and NOB Activity during Shortcut Nitrification in a Sequencing Batch Reactor in Terms of Energy Consumption Optimization
PublikacjaRecently, many wastewater treatment plants (WWTPs) have had to deal with serious problems related to the restrictive requirements regarding the euent quality, as well as significant energy consumption associated with it. In this situation, mainstream deammonification and/or shortened nitrification-denitrification via nitrite (so-called “nitrite shunt”) is a new promising strategy. This study shows the mechanisms and operating conditions...
-
Seasonal changes of mercury speciation in the coastal sediments
PublikacjaPurpose Mercury speciation in sediments is linked to environmental conditions and processes. Domination of particular mercury species depends on its source, displays considerable seasonal behavior, and may be further modified due to oxygen levels, icing conditions, or the input of fresh organic matter. The purpose of this study was to examine the coastal area of the Gulf of Gdańsk in terms of mercury contamination and the influence...
-
South African International Graph Theory Conference
Konferencje -
Linear game non-contextuality and Bell inequalities—a graph-theoretic approach
PublikacjaWe study the classical and quantum values of a class of one-and two-party unique games, that generalizes the well-known XOR games to the case of non-binary outcomes. In the bipartite case the generalized XOR(XOR-d) games we study are a subclass of the well-known linear games. We introduce a 'constraint graph' associated to such a game, with the constraints defining the game represented by an edge-coloring of the graph. We use the...
-
A Note on Shannon Capacity for Invariant and Evolving Channels
PublikacjaIn the paper we discuss the notion of Shannon capacity for invariant and evolving channels. We show how this notion is involved in information theory, graph theory and Ramsey theory.
-
The Urban Mentoring as a New Method of Participatory Urban Planning in Poland
PublikacjaTwenty-five years after the return of democracy and the beginning of basing the country's economy on neoliberal developmental paradigm, Poland adopted the regulations regarding management of urban policy, which had been wait for over a decade (accession to the EU). The National Urban Policy as well as the Act on revitalization have defined, in a modern manner, the field of cooperation between the local government, the administration...
-
Approximation algorithms for job scheduling with block-type conflict graphs
PublikacjaThe problem of scheduling jobs on parallel machines (identical, uniform, or unrelated), under incompatibility relation modeled as a block graph, under the makespan optimality criterion, is considered in this paper. No two jobs that are in the relation (equivalently in the same block) may be scheduled on the same machine in this model. The presented model stems from a well-established line of research combining scheduling theory...
-
Total Completion Time Minimization for Scheduling with Incompatibility Cliques
PublikacjaThis paper considers parallel machine scheduling with incompatibilities between jobs. The jobs form a graph equivalent to a collection of disjoint cliques. No two jobs in a clique are allowed to be assigned to the same machine. Scheduling with incompatibilities between jobs represents a well-established line of research in scheduling theory and the case of disjoint cliques has received increasing attention in recent...
-
Southeastern International Conference on Combinatorics, Graph Theory, and Computing
Konferencje -
Kyoto International Conference on Computational Geometry and Graph Theory
Konferencje -
Dataset of non-isomorphic graphs of the coloring types (K4,K4;n), 1<n<R(4,4)
Dane BadawczeFor 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...
-
Multi-agent graph searching and exploration algorithms
PublikacjaA team of mobile entities, which we refer to as agents or searchers interchangeably, starting from homebases needs to complete a given task in a graph.The goal is to build a strategy, which allows agents to accomplish their task. We analyze strategies for their effectiveness (e.g., the number of used agents, the total number of performed moves by the agents or the completion time).Currently, the fields of on-line (i.e., agents...
-
Marek Czachor prof. dr hab.
Osoby -
Global defensive sets in graphs
PublikacjaIn the paper we study a new problem of finding a minimum global defensive set in a graph which is a generalization of the global alliance problem. For a given graph G and a subset S of a vertex set of G, we define for every subset X of S the predicate SEC ( X ) = true if and only if | N [ X ] ∩ S | ≥ | N [ X ] \ S | holds, where N [ X ] is a closed neighbourhood of X in graph G. A set S is a defensive alliance if and only if for...
-
Progress on Roman and Weakly Connected Roman Graphs
PublikacjaA 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)....
-
Experimental and theoretical investigation of conformational states and noncovalent interactions in crystalline sulfonamides with a methoxyphenyl moiety
PublikacjaFour sulfonamide derivatives with a methoxyphenyl moiety, namely N-{4-[(2-methoxyphenyl)sulfamoyl] phenyl}acetamide (1a), N-{4-[(3-methoxyphenyl)sulfamoyl]phenyl}acetamide (1b), 4-amino-N-(2- methoxyphenyl)benzenesulfonamide (2a) and 4-amino-N-(3-methoxyphenyl)benzenesulfonamide (2b), have been synthesized and characterized physiochemically by CHNS, MS, FT-IR, 1H NMR, 13C NMR, PXRD and TG methods. Crystal structures were determined...
-
Modelling AOB-NOB competition in shortcut nitrification compared with conventional nitrification-denitrification process
PublikacjaIn particular, mainstream deammonification and/or shortened nitrificationdenitrification via nitrite (so-called “nitrite shunt”) is a promising new treatment concept that has the potential to revolutionise how nitrogen removal is achieved at WWTPs. Understanding the role of the AOB/NOB competition in the nitrogen cycle in wastewater treatment systems will change operational strategies of the novel nitrogen removal processes. The...
-
Persulfates to degrade a mixture of dyes (rhodamine B, methylene blue) in the presence of glucose and visible light
PublikacjaA treatment process utilizing visible-light-activated (Vis) persulfates (PS) in the presence of an organic promoter (glucose) was developed for the simultaneous decolorization of a rhodamine B (RhB) and methylene blue (MB) mixture. Various doses of glucose, PS concentrations, pH values, initial dye concentrations and process time were tested to find out the most appropriate parameters for degrading the RhB/MB mixture in the...
-
Noise Analysis of Continuous GPS Time Series of Selected EPN Stations to Investigate Variations in Stability of Monument Types
PublikacjaThe type of monument that a GPS antenna is placed on plays a significant role in noise estimation for each permanent GPS station. In this research 18 Polish permanent GPS stations that belong to the EPN (EUREF Permanent Network) were analyzed using Maximum Likelihood Estimation (MLE). The antennae of Polish EPN stations are placed on roofs of buildings or on concrete pillars. The analyzed data covers a period of 5 years from 2008...
-
On Computational Aspects of Greedy Partitioning of Graphs
PublikacjaIn 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...
-
Dynamics of S-unimodal maps used in population modeling.
Dane BadawczeS-unimodal maps are maps of the interval with negative Schwarzian derivative and having only one turning point (such that the map is increasing to the left of the turning point and decreasing to the right of it). Theory of S-unimodal maps is now a well-developed branch of discrete dynamical systems, including famous Singer theorem which implies existence...
-
On Tradeoffs Between Width- and Fill-like Graph Parameters
PublikacjaIn this work we consider two two-criteria optimization problems: given an input graph, the goal is to find its interval (or chordal) supergraph that minimizes the number of edges and its clique number simultaneously. For the interval supergraph, the problem can be restated as simultaneous minimization of the path width pw(G) and the profile p(G) of the input graph G. We prove that for an arbitrary graph G and an integer t ∈ {1,...
-
Computational aspects of greedy partitioning of graphs
PublikacjaIn 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...
-
Infinite chromatic games
PublikacjaIn 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...
-
Dataset of non-isomorphic graphs being coloring types (K5-e,Km-e;n), 2<m<5, 1<n<R(K5-e,Km-e)
Dane BadawczeFor 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)
Dane BadawczeFor 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)
Dane BadawczeFor 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)...
-
Brushing with additional cleaning restrictions
PublikacjaIn 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...
-
Application of genetic algorithms in graph searching problem
PublikacjaGraph searching is a common approach to solving a problem of capturing a hostile intruder by a group of mobile agents. We assume that this task is performed in environment which we are able to model as a graph G. The question asked is how many agents are needed to capture an arbitrary fast, invisible and smart intruder. This number is called the (edge) search number of G. The strategy which must be performed by agents is called...
-
Dataset of non-isomorphic graphs of the coloring types (Km,K3-e;n), 4<m<8, 1<n<R(Km,K3-e)
Dane BadawczeFor 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)...
-
5-Selenocyanato and 5-trifluoromethanesulfonyl derivatives of 2′-deoxyuridine: synthesis, radiation and computational chemistry as well as cytotoxicity
Publikacja5-Selenocyanato-2′-deoxyuridine (SeCNdU) and 5-trifluoromethanesulfonyl-2′-deoxyuridine (OTfdU) have been synthesized and their structures have been confirmed with NMR and MS methods. Both compounds undergo dissociative electron attachment (DEA) when irradiated with X-rays in an aqueous solution containing a hydroxyl radical scavenger. The DEA yield of SeCNdU significantly exceeds that of 5-bromo-2′-deoxyuridine (BrdU), remaining...
-
THE INFLUENCE OF WATER-LAND RELATIONS ON THE LANDSCAPE AND ARCHITECTURE OF THE VISTULA DELTA (POLAND)
PublikacjaThe Vistula Delta is unique region of water domination. In this part of Europe, historic rural assumptions have been developing since the 12th century. Practically, it can be said that most of the systems were related to the coexistence of the human and the water element. Relations of water and land, developed specific types of villages such as a water-based village. Water landscape; polders, canals, dikes and rivers, hydro-technical...
-
On extremal sizes of locally k-tree graphs
PublikacjaA 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...
-
Graphs with isolation number equal to one third of the order
PublikacjaA set D of vertices of a graph G is isolating if the set of vertices not in D and with no neighbor in D is independent. The isolation number of G, denoted by \iota(G) , is the minimum cardinality of an isolating set of G. It is known that \iota(G) \leq n/3 , if G is a connected graph of order n, , distinct from C_5 . The main result of this work is the characterisation of unicyclic and block graphs of order n with isolating number...
-
A collection of directed graphs for the minimum cycle mean weight computation
Dane BadawczeThis 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...
-
2-Coloring number revisited
Publikacja2-Coloring number is a parameter, which is often used in the literature to bound the game chromatic number and other related parameters. However, this parameter has not been precisely studied before. In this paper we aim to fill this gap. In particular we show that the approximation of the game chromatic number by the 2-coloring number can be very poor for many graphs. Additionally we prove that the 2-coloring number may grow...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km-e;n), 2<m<7, 1<n<R(K3,Km-e).
Dane BadawczeFor 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)...
-
Dataset of non-isomorphic graphs of the coloring types (K3,Km;n), 2<m<7, 1<n<R(3,m)
Dane BadawczeFor 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...
-
Minimum order of graphs with given coloring parameters
PublikacjaA 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),...
-
Paweł Szymon Dąbrowski dr inż.
OsobyDr inż. Paweł Szymon Dąbrowski w latach 2004-2009 studiował na kierunku geodezja i kartografia na Uniwersytecie Warmińsko-Mazurskim w Olsztynie, gdzie uzyskał tytuł zawodowy magistra inżyniera. W latach 2009-2016 pracował w wykonawstwie geodezyjnym w Iławie i Gdańsku. Doświadczenie zawodowe zdobył on podczas realizacji inwestycji Pomorskiej Kolei Metropolitalnej, co pomogło mu w zdobyciu w 2015 r. geodezyjnych uprawnień zawodowych...
-
Dataset of non-isomorphic graphs being coloring types (K4-e,Km-e;n), 2<m<7, 1<n<R(K4-e,Km-e)
Dane BadawczeFor 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...
-
Scheduling with Complete Multipartite Incompatibility Graph on Parallel Machines: Complexity and Algorithms
PublikacjaIn this paper, the problem of scheduling on parallel machines with a presence of incompatibilities between jobs is considered. The incompatibility relation can be modeled as a complete multipartite graph in which each edge denotes a pair of jobs that cannot be scheduled on the same machine. The paper provides several results concerning schedules, optimal or approximate with respect to the two most popular criteria of optimality:...
-
Distribution and bioavailability of mercury in the surface sediments of the Baltic Sea
PublikacjaThe study aimed to determine the level of mercury (Hg) and its labile and stable forms in the surface sediments of the Baltic Sea. The work considers the impact of current and historical sources of Hg on sediment pollution, together with the influence of different environmental parameters, including water inflows from the North Sea. Surface sediments (top 5 cm) were collected in 2016–2017 at 91 stations located in different...
-
Equitable coloring of corona products of graphs
PublikacjaIn 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.
-
Constructing a map of an anonymous graph: applications of universal sequences
PublikacjaWe study the problem of mapping an unknown environmentrepresented as an unlabelled undirected graph. A robot (or automaton)starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria...
-
Dataset of non-isomorphic graphs being coloring types (K3-e,Km-e;n), 2<m<8, 1<n<R(K3-e,Km-e)
Dane BadawczeFor 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...
-
Minimal number of periodic points for smooth self-maps of simply-connected manifolds
Dane BadawczeThe problem of finding the minimal number of periodic points in a given class of self-maps of a space is one of the central questions in periodic point theory. We consider a closed smooth connected and simply-connected manifold of dimension at least 4 and its self-map f. The topological invariant D_r[f] is equal to the minimal number of r-periodic points...
-
The Backbone Coloring Problem for Small Graphs
PublikacjaIn this paper we investigate the values of the backbone chromatic number, derived from a mathematical model for the problem of minimization of bandwidth in radio networks, for small connected graphs and connected backbones (up to 7 vertices). We study the relationship of this parameter with the structure of the graph and compare the results with the solutions obtained using the classical graph coloring algorithms (LF, IS), modified...
-
Leader election for anonymous asynchronous agents in arbitrary networks
PublikacjaWe 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...
-
Janusz Nieznański prof. dr hab. inż.
OsobyUrodził się w 1957 r. w Gdańsku. Jest absolwentem Wydziału Elektrycznego Politechniki Gdańskiej (1981). W 1990 r. uzyskał stopień doktora, w 1999 r. stopień doktora habilitowanego, a w 2015 r. tytuł profesora. Jest pracownikiem naukowo-dydaktycznym Politechniki Gdańskiej nieprzerwanie od ukończenia studiów. Jego zainteresowania naukowe obejmują sterowanie, diagnostykę, modelowanie i symulację układów energoelektronicznych i napędowych,...
-
Workshop on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks
Konferencje -
Exploiting multi-interface networks: Connectivity and Cheapest Paths
PublikacjaLet G = (V,E) be a graph which models a set of wireless devices (nodes V) that can communicate by means of multiple radio interfaces, according to proximity and common interfaces (edges E). The problem of switching on (activating) the minimum cost set of interfaces at the nodes in order to guarantee the coverage of G was recently studied. A connection is covered (activated) when the endpoints of the corresponding edge share at...
-
Dynamic F-free Coloring of Graphs
PublikacjaA 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...
-
Three-fast-searchable graphs
PublikacjaIn the edge searching problem, searchers move from vertex to vertex in a graph to capture an invisible, fast intruder that may occupy either vertices or edges. Fast searching is a monotonic internal model in which, at every move, a new edge of the graph G must be guaranteed to be free of the intruder. That is, once all searchers are placed the graph G is cleared in exactly |E(G)| moves. Such a restriction obviously necessitates...
-
Bounds on the Cover Time of Parallel Rotor Walks
PublikacjaThe rotor-router mechanism was introduced as a deterministic alternative to the random walk in undirected graphs. In this model, a set of k identical walkers is deployed in parallel, starting from a chosen subset of nodes, and moving around the graph in synchronous steps. During the process, each node maintains a cyclic ordering of its outgoing arcs, and successively propagates walkers which visit it along its outgoing arcs in...
-
Decontaminating Arbitrary Graphs by Mobile Agents: a Survey
PublikacjaA 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...
-
A Systematic Search for New Coupling Schemes of Cross-Coupled Resonator Bandpass Filters
PublikacjaIn this paper, a systematic approach to an extensive search for topologies of cross-coupled filters with generalized Chebyshev response is presented. The technique applies graph theory to find unique, nonisomorphic filter configurations, and tests whether a specific frequency response can be realized in a given set of topologies. The results of the search are then stored in a database of possible filter configurations.
-
On-line ranking of split graphs
PublikacjaA vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm...