Search
Filters
total: 1029
displaying 1000 best results Help
Search results for: GRAPH INVARIANTS
-
JOURNAL OF GRAPH THEORY
Journals -
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...
-
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),...
-
Association of polymorphic variants in GEMIN genes with the risk of depression in a Polish population
Publication -
Association of Polymorphic Variants in Argonaute Genes with Depression Risk in a Polish Population
Publication -
Association of circadian clock TIMELESS variants and expression with asthma risk in children
Publication -
MC1R common variants, CDKN2A and their association with melanoma and breast cancer risk
Publication -
Expression of alternatively spliced variants of the Dclk1 gene is regulated by psychotropic drugs
Publication -
Splice variants of mitofusin 2 shape the endoplasmic reticulum and tether it to mitochondria
PublicationIn eukaryotic cells, different organelles interact at membrane contact sites stabilized by tethers. Mitochondrial mitofusin 2 (MFN2) acts as a membrane tether that interacts with an unknown partner on the endoplasmic reticulum (ER). In this work, we identified the MFN2 splice variant ERMIT2 as the ER tethering partner of MFN2. Splicing of MFN2 produced ERMIT2 and ERMIN2, two ER-specific variants. ERMIN2 regulated ER morphology,...
-
Ranking decision variants by subjective paird comparisons in cases with incomplete data.
PublicationMetoda porównań parami wykorzystywana jest do szeregowania skończonej,zwykle niewielkiej liczby wariantów decyzyjnych. W metodzie tej ekspert lub grupa ekspertów proszona jest o wyrażenie swojej opinii dotyczącej każdej pary wariantów w postaci względnej preferenecji jednego wariantu nad drugim.Zdarza się jednak często, że ekspert nie jest w stanie ocenić pary lub par wiariantów i mamy wtedy do czynienia z sytuacją...
-
Similarities and Differences Between the Vertex Cover Number and the Weakly Connected Domination Number of a Graph
PublicationA vertex cover of a graph G = (V, E) is a set X ⊂ V such that each edge of G is incident to at least one vertex of X. The ve cardinality of a vertex cover of G. A dominating set D ⊆ V is a weakly connected dominating set of G if the subgraph G[D]w = (N[D], Ew) weakly induced by D, is connected, where Ew is the set of all edges having at least one vertex in D. The weakly connected domination number γw(G) of G is the minimum cardinality...
-
Application of Graph Theory Algorithms in Non-disjoint Functional Decomposition of Specific Boolean Functions
Publication -
Session-Based Recommendation with Graph Neural Networks with an Examination of the Impact of Local and Global Vectors
PublicationThis study investigates the application of graph neural networks (GNN) in session-based recommendation systems (SR), focusing on a key modification involving the use of a global vector. Session-based recommendation systems often face challenges in accurately capturing user behavior due to the limited data available within individual sessions. The SR-GNN model, originally designed for automatic feature extraction from session graphs...
-
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...
-
Grape vinegars – characteristics, properties and safety of use
Publication -
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...
-
SELECTED ASPECTS OF THE EVALUATION OF THE QUALITY OF GRAPE WINE
PublicationDevelopment of the domestic grape wine market has been presented. The number of grape wine producing entities, acreage, and volume of production over last five years are presented. The composition of red grape wine has been discussed involving health promoting aspects. Two methods of wine quality determination: analytical and sensory meth ods have been described. Physicochemical parameters influencing wine quali ty (acidity, sweetness)...
-
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...
-
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...
-
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.
-
Time reversal invariant single-gap superconductivity with upper critical field larger than the Pauli limit in NbIr2B2
PublicationRecently, compounds with noncentrosymmetric crystal structure have attracted much attention for providing a rich playground in search for unconventional superconductivity. NbIr2B2 is a new member to this class of materials harboring superconductivity below Tc = 7.3(2) K and a very high upper critical field that exceeds Pauli limit. Here we report on muon spin rotation (μSR) experiments probing the temperature and field dependence...
-
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...
-
CAUSALITY IN MODELS OF THERMAL PROCESSES IN SHIP ENGINE ROOMS WITH THE USE OF BOND GRAPH (BG) METHOD
PublicationWith a single approach to modeling elements of different physical nature, the method of Bond Graph (BG) is particularly well suited for modeling energy systems consisting of mechanical, thermal, electrical and hydraulic elements that operate in the power system engine room. The paper refers to the earlier presented new concept of thermal process modeling using the BG method. The authors own suggestions for determining causality...
-
Studies on the influence of technological variants of finishing machining on flow of parts in flexible manufacturing
PublicationIn the article below the problems of influence of variants of finishing processing on flow of machining parts in flexible manufacturing system were presented. The investigations were carried out the technological processes for piston rods and rams of hydraulic cylinders. There were also presented model variants of technological processes for piston rods finished with the burnishing. In these studies the influence of technological...
-
Comparative analysis of selected design variants of propulsion system for an inland waterways ship
PublicationW pracy zaprezentowano założenia projektowe i wstępną analizę porównawczą dwóch wariantów napędu śródlądowego statku pasażerskiego. Pierwsze rozwiązanie to wariant z przekładnią elektryczną, drugie natomiast, to wariant z przekładnią hydrostatyczną.
-
Ciliary phenotyping in renal epithelial cells in a cranioectodermal dysplasia patient with WDR35 variants
Publication -
Quechers sample preparation method variants for analysis of pesticide residues in fruits and vegetables
PublicationThis article describes the comparison of different versions of an easy, rapid and low-cost sample preparation approach for the determination of pesticide residues in fruits and vegetables by concurrent use of gas and liquid chromatography coupled to MS or ECD for detection. The sample preparation approach is known as QuEChERS, which stands for quick, easy, cheap, effective, rugged and safe. It is a combination of liquid-liquid...
-
Variants and Modifications of the Retroauricular Approach Using in Temporomandibular Joint Surgery: A Systematic Review
Publication -
Molecular insights into receptor binding energetics and neutralization of SARS-CoV-2 variants
Publication -
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...