Search
Search results for: GRAPH
-
International Conference on Graph Transformations
Conferences -
Workshop on Probabilistic Graph Theory
Conferences -
Graphitic carbon nitride/graphene oxide/reduced graphene oxide nanocomposites for photoluminescence and photocatalysis
Publication -
Parity vertex colouring of graphs
PublicationA 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-line P-coloring of graphs
PublicationFor a given induced hereditary property P, a P-coloring of a graph G is an assignment of one color to each vertex such that the subgraphs induced by each of the color classes have property P. We consider the effectiveness of on-line P-coloring algorithms and give the generalizations and extensions of selected results known for on-line proper coloring algorithms. We prove a linear lower bound for the performance guarantee function...
-
Some variations of perfect graphs
PublicationWe 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...
-
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.
-
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.
-
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...
-
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 -
Total domination in versus paired-domination in regular graphs
PublicationA subset S of vertices of a graph G is a dominating set of G if every vertex not in S has a neighbor in S, while S is a total dominating set of G if every vertex has a neighbor in S. If S is a dominating set with the additional property that the subgraph induced by S contains a perfect matching, then S is a paired-dominating set. The domination number, denoted γ(G), is the minimum cardinality of a dominating set of G, while the...
-
Block graphs with large paired domination multisubdivision number
PublicationThe paired domination multisubdivision number of a nonempty graph G, denoted by msdpr(G), is the smallest positive integer k such that there exists an edge which must be subdivided k times to increase the paired domination number of G. It is known that msdpr(G) ≤ 4 for all graphs G. We characterize block graphs with msdpr(G) = 4.
-
Optimal backbone coloring of split graphs with matching backbones
PublicationFor 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.
-
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.
-
Domination numbers in graphs with removed edge or set of edges
PublicationW artykule przedstawiony jest wpływ usuwania krawędzi lub zbioru krawędzi na liczby dominowania spójnego i słabo spójnego.
-
GRAPHS AND COMBINATORICS
Journals -
On incidence coloring of coloring of complete multipartite and semicubic bipartite graphs
PublicationIn 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.
-
A note on polynomial algorithm for cost coloring of bipartite graphs with Δ ≤ 4
PublicationIn the note we consider vertex coloring of a graph in which each color has an associated cost which is incurred each time the color is assigned to a vertex. The cost of coloring is the sum of costs incurred at each vertex. We show that the minimum cost coloring problem for n-vertex bipartite graph of degree ∆≤4 can be solved in O(n^2) time. This extends Jansen’s result [K.Jansen,The optimum cost chromatic partition problem, in:...
-
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
Publication -
Efficient list cost coloring of vertices and/or edges of bounded cyclicity graphs
PublicationW artykule rozważamy listowo-kosztowe kolorowanie wierzchołków i krawędzi grafu w modelu wierzchołkowym, krawędziowym, totalnym i pseudototalnym. Stosujemy programowanie dynamiczne w celu otrzymania algorytmów wielomianowych dla drzew. Następnie uogólniamy to podejście na dowolne grafy z ograniczonymi liczbami cyklomatycznymi i na ich multikolorowania.
-
Controlled oxidation of graphite to graphene oxide with novel oxidants in a bulk scale
Publication -
Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
PublicationW pracy rozważamy problem szukania, dla danego grafu prostego, drzewa spinającego, którego uporządkowana liczba chromatyczna jest minimalna. K.~Miyata i inni dowiedli w [Np-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem,Discrete Appl. Math. 154 (2006) 2402-2410], że odpowiedni problem decyzyjny jest NP-trudny już w przypadku pytania o istnienie uporządkowanego 4-pokolorowania....
-
South African International Graph Theory Conference
Conferences -
Laser-Induced Graphitization of Polydopamine on Titania Nanotubes
PublicationSince the discovery of laser-induced graphite/graphene, there has been a notable surge of scientific interest in advancing diverse methodologies for their synthesis and applications. This study focuses on the utilization of a pulsed Nd:YAG laser to achieve graphitization of polydopamine (PDA) deposited on the surface of titania nanotubes. The partial graphitization is corroborated through Raman and XPS spectroscopies and supported...
-
Engineering Graphics I, PG_00055216
e-Learning Courses -
Engineering Graphics II, PG_00040167
e-Learning CoursesEngineering Graphics
-
Southeastern International Conference on Combinatorics, Graph Theory, and Computing
Conferences -
Kyoto International Conference on Computational Geometry and Graph Theory
Conferences -
International Workshop on Graph-Theoretic Concepts in Computer Science
Conferences -
GRAPHICAL MODELS
Journals -
Graphomotor functions in ADHD – motor or planning deficit? A microgenetic approach
Publication -
On the graphitisation role of oxide supports in carbon nanotube CVD synthesis
Publication -
Engineer's graphic workshop. Historical review.
PublicationThe paper introduces the history of development of graphic engineering workshop within European culture. The fundamentals of scientific approach to this subject are dated back to the XVIII century. Owning to Gaspard Monge's works descriptive geometry rose to the rank of branch of mathematics. As the time passes we observe the endeavors aiming at accelerating and automating the process of engineering drawing. Since the XX century...
-
Impossible objects in geometry and graphic education
PublicationW artykule przedstawiono propozycję wprowadzenia do programu nauczania z geometrii przestrzennej i grafiki inżynierskiej obiektów niemożliwych (tworzonych między innymi przez M.C. Eschera). Celem analizy fenomenu obiektów niemożliwych w kontekście odwzorowań płaskich obiektów przestrzennych, a także percepcji przestrzeni jest wzbogacenie wyobrażni przestrzennej i kreatywności studentów.
-
The Potential of Greed for Independence
PublicationThe 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...
-
Engineering Graphics I, PG_00055216 2024/25
e-Learning Courses -
Engineering Graphics I, PG_00055216 2023/24
e-Learning Courses -
Smart Pen - new multimodal computer control tool for graphomotorical therapy
PublicationW sytuacji, gdy około 15% populacji uczniów wykazuje cechy dyslektyczne, koniecznością staje się wyposażenie szkół w efektywne narzędzia do diagnozy i terapii tego rodzaju zaburzeń. Dzięki wykorzystaniu tabletu i specjalnie skonstruowanego długopisu wyposażonego w czujniki nacisku uzyskano możliwość monitorowania wielu parametrów, które do tej pory były dla terapeutów całkowicie niedostępne (np. pomiar nacisku na podłoże czy ścisku...
-
Stereoscopy in Graphics APIs for CAVE Applications
PublicationThe paper compares the advantages and disadvantages of a variety of Graphics Application Programming Interfaces (APIs) from the perspective of obtaining stereoscopy in applications written for a CAVE virtual reality environment. A number of problems have been diagnosed and an attempt has been made to solve them using OpenGL, DirectX 11 and 12, Vulkan, as well as the Unity Engine which can internally use DirectX, OpenGL and Vulkan,...
-
Relativistic hydrodynamics on graphics processing units
Publication -
Low-Temperature Exfoliated Graphenes: Vacuum-Promoted Exfoliation and Electrochemical Energy Storage
Publication -
Workshop on Applications of Graph Theory in Wireless Ad hoc Networks and Sensor Networks
Conferences -
Engineering Graphics II (M:31997W1) 2023/24
e-Learning CoursesThe course covers subject scope of standardised methods used for the presentation of machine details in projected views, in technical design drawings. Detailed topics include: projection systems, principles of design documentation in machine design, rules in dimensioning and selection of views in technical drawing. Practical excercises are carried out and an introduction to CAD is performed.
-
Mulimedia manuals for descriptive geometry and engineering graphics
PublicationThe article discusses issues connected with ICT (Information and Communication Technologies) implementation in Descriptive Geometry and Engineering Graphics Education. The presentation of the issues is supported by the author's multimedia manuals made in Multimedia Flash MX technology and published on the Gdańsk University of Technology net.
-
A facile strategy for reclaiming discarded graphite and harnessing the rate capabilities of graphite anodes
PublicationGraphite negative electrodes are unbeaten hitherto in lithium-ion batteries (LiBs) due to their unique chemical and physical properties. Thus, the increasing scarcity of graphite resources makes smart recycling or repurposing of discarded graphite particularly imperative. However, the current recycling techniques still need to be improved upon with urgency. Herein a facile and efficient hydrometallurgical process is reported to...
-
Theory and Applications of Graphs
Journals -
Quality of graphical markers for the needs of eyewear devices
Publicationin this paper we propose to cast the problem of identification of people, objects or places into an application for smart glasses that decodes information from graphical markers. We focus on analyzing different factors that can have influence on the processes of the automatic recognition of information from a code. The research we present aims at reviewing recognition performances in function of: size of a marker, distance from/to...