Discrete Applied Mathematics

Items from 1 to 20 out of 24 results

article

Neighbor sum distinguishing total choosability of planar graphs without 4-cycles

Jihui Wang, Jiansheng Cai, Qiaoling Ma

Discrete Applied Mathematics > 2016 > 206 > C > 215-219

Let G=(V,E) be a graph and ϕ be a total k-coloring of G by using the color set {1,…,k}. Let ∑ϕ(u) denote the sum of the color of the vertex u and the colors of all incident edges of u. A k-neighbor sum distinguishing total coloring of G is a total k-coloring of G such that for each edge uv∈E(G), ∑ϕ(u)≠∑ϕ(v). By χΣ″(G), we denote the smallest value k in such a coloring of G. Pilśniak and Woźniak first...

article

On r-dynamic coloring of graphs

Sogol Jahanbekam, Jaehoon Kim, Suil O, Douglas B. West

Discrete Applied Mathematics > 2016 > 206 > C > 65-72

An r-dynamic proper k-coloring of a graph G is a proper k-coloring of G such that every vertex in V(G) has neighbors in at least min{d(v),r} different color classes. The r-dynamic chromatic number of a graph G, written χr(G), is the least k such that G has such a coloring. By a greedy coloring algorithm, χr(G)≤rΔ(G)+1; we prove that equality holds for Δ(G)>2 if and only if G is r-regular with diameter...

article

Discrete Applied Mathematics > 2016 > 206 > C > v-vi

article

On the further relation between the (revised) Szeged index and the Wiener index of graphs

Huihui Zhang, Shuchao Li, Lifang Zhao

Discrete Applied Mathematics > 2016 > 206 > C > 152-164

In 2010, Hansen et al. proposed three conjectures on the differences between the (revised) Szeged index and the Wiener index for a connected graph G. Recently, the above conjectures were solved by Chen et al. (2014). In this paper, as a continuance of it, we study some further relation between the (revised) Szeged index and Wiener index of connected graphs. Some sharp bounds on the difference between...

article

On Wiener and multiplicative Wiener indices of graphs

Kinkar Ch. Das, Ivan Gutman

Discrete Applied Mathematics > 2016 > 206 > C > 9-14

Let G be a connected graph of order n with m edges and diameter d. The Wiener index W(G) and the multiplicative Wiener index π(G) of the graph G are equal, respectively, to the sum and product of the distances between all pairs of vertices of G. We obtain a lower bound for the difference π(G)−W(G) of bipartite graphs. From it, we prove that π(G)>W(G) holds for all connected bipartite graphs, except...

article

The maximum matching energy of bicyclic graphs with even girth

Gang Ma, Shengjin Ji, Qiuju Bian, Xia Li

Discrete Applied Mathematics > 2016 > 206 > C > 203-210

The matching energy of a graph was introduced by Gutman and Wagner in 2012 and defined as the sum of the absolute values of zeros of its matching polynomial. In this paper, we characterize the graphs with maximum matching energy among all bicyclic graphs with even girth.

article

Detour trees

Adam S. Jobson, André E. Kézdy, Jenő Lehel, Susan C. White

Discrete Applied Mathematics > 2016 > 206 > C > 73-80

A detour of a graph is a path of maximum length. A vertex that is common to all detours of a graph is called a Gallai vertex. As a tool to prove the existence of a Gallai vertex, we introduce the concept of a detour tree, a spanning tree of a graph in which the vertex set of any detour of the graph induces a subtree. We give several characterizations of graphs that have a detour tree. We also prove...

article

Intersection graphs of L-shapes and segments in the plane

Stefan Felsner, Kolja Knauer, George B. Mertzios, Torsten Ueckerdt

Discrete Applied Mathematics > 2016 > 206 > C > 48-55

An L-shape is the union of a horizontal and a vertical segment with a common endpoint. These come in four rotations: , , and . A k-bend path is a simple path in the plane, whose direction changes k times from horizontal to vertical. If a graph admits an intersection representation in which every vertex is represented by an , an or , a k-bend path, or a segment, then this graph is called an {}-graph,...

article

On the extreme eccentric distance sum of graphs with some given parameters

Shuchao Li, Yueyu Wu

Discrete Applied Mathematics > 2016 > 206 > C > 90-99

The eccentric distance sum (EDS) of a connected graph G is defined as ξd(G)=∑v∈VG(εG(u)+εG(v))dG(u,v), where εG(⋅) is the eccentricity of the corresponding vertex and dG(u,v) is the distance between the vertices u and v. The eccentric distance sum is a novel graph invariant with vast potential in structure activity/property relationships. In this paper, the relationship between the EDS and some other...

article

Improving the characterization of P-stability for applications in network privacy

Julián Salas, Vicenç Torra

Discrete Applied Mathematics > 2016 > 206 > C > 109-114

Recently, we have found that the concept of P-stability has interesting applications in network privacy. In the context of Online Social Networks it may be used for obtaining a fully polynomial randomized approximation scheme for graph masking and measuring disclosure risk. Also by using the characterization for P-stable sequences from Jerrum, McKay and Sinclair (1992) it is possible to obtain optimal...

article

House-swapping with divorcing and engaged pairs

Katarína Cechlárová, Tamás Fleiner, Zsuzsanna Jankó

Discrete Applied Mathematics > 2016 > 206 > C > 1-8

We study a real-life modification of the classical house-swapping problem that is motivated by the existence of engaged pairs and divorcing couples. We show that the problem of finding a new house for the maximum number of agents is inapproximable, but fixed-parameter tractable.

article

On the geodetic iteration number of the contour of a graph

Mauro Mezzini

Discrete Applied Mathematics > 2016 > 206 > C > 211-214

Let G be a graph and S be a subset of vertices of G. With I[S] we denote the set of all vertices on some geodesic (shortest path) between two vertices of S. A contour vertex of a graph is one whose eccentricity is at least as big as all its neighbors’ eccentricities. Let C be the set of contour vertices of a graph. We provide the first example of a graph where I[I[C]] do not coincide with the vertex...

article

Largest domination number and smallest independence number of forests with given degree sequence

Michael Gentner, Michael A. Henning, Dieter Rautenbach

Discrete Applied Mathematics > 2016 > 206 > C > 181-187

For a sequence d of non-negative integers, let F(d) be the set of all forests whose degree sequence is d. We present closed formulas for γmaxF(d)=max{γ(F):F∈F(d)} and αminF(d)=min{α(F):F∈F(d)} where γ(F) and α(F) are the domination number and the independence number of a forest F, respectively.

article

Complexity aspects of the triangle path convexity

Mitre C. Dourado, Rudini M. Sampaio

Discrete Applied Mathematics > 2016 > 206 > C > 39-47

In a triangle path v1,…,vt of a graph G no edges exist joining vertices vi and vj such that |j−i|>2. A set S⊆V(G) is convex in the triangle path convexity of G, or t-convex, if the vertices of every triangle path joining two vertices of S are in S. The cardinality of a maximum proper t-convex subset of V(G) is the t-convexity number of G and the cardinality of a minimum set of vertices whose...

article

Disjoint Hamilton cycles in transposition graphs

Walter Hussak

Discrete Applied Mathematics > 2016 > 206 > C > 56-64

Most network topologies that have been studied have been subgraphs of transposition graphs. Edge-disjoint Hamilton cycles are important in network topologies for improving fault-tolerance and distribution of messaging traffic over the network. Not much was known about edge-disjoint Hamilton cycles in general transposition graphs until recently Hung produced a construction of 4 edge-disjoint Hamilton...

article

On the uniqueness of some girth eight algebraically defined graphs

Brian G. Kronenthal, Felix Lazebnik

Discrete Applied Mathematics > 2016 > 206 > C > 188-194

Let F be a field. For a polynomial f∈F[x,y], we define a bipartite graph ΓF(f) with vertex partition P∪L, P=F3=L, and (p1,p2,p3)∈P is adjacent to [l1,l2,l3]∈L if and only if p2+l2=p1l1andp3+l3=f(p1,l1). It is known that the graph ΓF(xy2) has no cycles of length less than eight. The main result of this paper is that ΓF(xy2) is the only graph ΓF(f) with this property when F is an algebraically closed...

article

Pattern restricted Stirling k-ary words, the plateau statistic and the kernel method

Shi-Mei Ma, Toufik Mansour

Discrete Applied Mathematics > 2016 > 206 > C > 100-108

Stirling k-ary words resemble classical Stirling permutations except that all entries of a Stirling k-ary word of length n belong to the set {1,2,…,k}. We first study generating functions for the number of pattern restricted Stirling k-ary words with a given number of plateaux by using the kernel method. We then study the generating function for the number of Stirling k-ary words of length n according...

article

On del-robust primitive words

Amit Kumar Srivastava, Ananda Chandra Nayak, Kalpesh Kapoor

Discrete Applied Mathematics > 2016 > 206 > C > 115-121

A word is said to be primitive if it cannot be expressed as non-trivial power of another word. We characterize a class of primitive words, referred as del-robust primitive words, which remain primitive on deletion of any letter. It is also shown that the language of primitive words that are not del-robust is not context-free. Finally, we present a linear time algorithm to recognize del-robust primitive...

article

Dynamic coloring of graphs having no K5 minor

Younjin Kim, Sang June Lee, Sang-il Oum

Discrete Applied Mathematics > 2016 > 206 > C > 81-89

We prove that every simple connected graph with no K5 minor admits a proper 4-coloring such that the neighborhood of each vertex v having more than one neighbor is not monochromatic, unless the graph is isomorphic to the cycle of length 5. This generalizes the result on planar graphs by S.-J. Kim, W.-J. Park and the second author [Discrete Appl. Math. 161 (2013) 2207–2212].

article

Clique cover products and unimodality of independence polynomials

Bao-Xuan Zhu

Discrete Applied Mathematics > 2016 > 206 > C > 172-180

Given two graphs G and H, assume that C={C1,C2,…,Cq} is a clique cover of G and U is a subset of V(H). We introduce a new graph operation called the clique cover product, denoted by GC⋆HU, as follows: for each clique Ci∈C, add a copy of the graph H and join every vertex of Ci to every vertex of U. We prove that the independence polynomial of GC⋆HUI(GC⋆HU;x)=[I(H;x)]qI(G;xI(H−U;x)I(H;x)), which generalizes...

Volume:
206
Year:
2016

Publication date

Set your own date range

Number

C (24)

Keywords

BICYCLIC GRAPH (2)
DEGREE SEQUENCE (2)
DYNAMIC COLORING (2)
WIENER INDEX (2)
(XYAB)-TRANSFORMATION (1)
ADJACENCY POLYNOMIAL (1)
ALGEBRAICALLY DEFINED GRAPH (1)
AUTOMORPHISMS (1)
CACTUS (1)
CHOOSABILITY (1)
CLIQUE (1)
CO-PLANAR GRAPHS (1)
COGRAPHS (1)
COMBINATORIAL NULLSTELLENSATZ (1)
COMBINATORICS ON WORDS (1)
COMPATIBLE TREES (1)
CONDITIONAL INDEPENDENCE (1)
CONNECTIVITY (1)
CONTEXT-FREE LANGUAGE (1)
CONTOUR OF A GRAPH (1)
CONVEXITY NUMBER (1)
CORE (1)
COSPECTRAL DIGRAPHS (1)
CYCLE (1)
DEL-ROBUST (1)
DIAMETER (1)
DIAMETER (OF GRAPH) (1)
DISTANCE (IN GRAPH) (1)
DISTANCE SPECTRAL RADIUS (1)
DISTANCE SPREAD (1)
DOMINATING SET (1)
DUALLY CHORDAL GRAPHS (1)
ECCENTRIC DISTANCE SUM (1)
EDGE-DISJOINT HAMILTON CYCLES (1)
EVEN GIRTH (1)
FINITE FIELD (1)
FIXED-PARAMETER TRACTABILITY (1)
FORCING NUMBER (1)
FOREST REALIZATION (1)
FOUR COLOR THEOREM (1)
FPRAS (1)
FULLY POLYNOMIAL-TIME RANDOMIZED APPROXIMATION SCHEME (1)
GENERALIZED PERMUTOHEDRON (1)
GENERALIZED QUADRANGLE (1)
GEODESIC CONVEXITY (1)
GEODETIC ITERATION NUMBER (1)
GIRTH EIGHT (1)
GRAPH COLORING (1)
GRAPH CONVEXITY (1)
GRAPHIC SEQUENCE (1)
HADWIGER’S CONJECTURE (1)
HELLY PROPERTY (1)
HOUSE-SWAPPING (1)
HULL NUMBER (1)
INAPPROXIMABILITY (1)
INDECOMPOSABLE POLYTOPE (1)
INDEPENDENCE POLYNOMIALS (1)
INDEPENDENT SET (1)
INTERSECTING LONGEST CYCLES (1)
INTERSECTING LONGEST PATHS (1)
INTERSECTION GRAPHS (1)
ISOMETRIC CYCLE (1)
K-ANONYMITY (1)
K-BEND VPG-GRAPHS (1)
KERNEL METHOD (1)
LEAST DISTANCE EIGENVALUE (1)
LEFSCHETZ PRINCIPLE (1)
LOG-CONCAVITY (1)
MATCHING ENERGY (1)
MINOR-FREE GRAPH (1)
MULTIPLICATIVE WIENER INDEX (1)
NEIGHBOR SUM DISTINGUISHING TOTAL COLORING (1)
NON-BIPARTITE GRAPH (1)
P-STABILITY (1)
PERFECT MATCHING (1)
PLANAR 3-TREES (1)
PLANAR GRAPH (1)
PLATEAUX (1)
POLYOMINO GRAPH (1)
PRIMITIVE WORDS (1)
RAPIDLY MIXING MARKOV CHAIN (1)
REAL ZEROS (1)
REALIZATION (1)
REFLECTIVE (1)
REGULAR DIGRAPH (1)
RESONANT SET (1)
REVISED SZEGED INDEX (1)
SEGMENT GRAPHS (1)
STAR GRAPHS (1)
STIRLING K-ARY WORDS (1)
STIRLING PERMUTATIONS (1)
SUBMODULAR FUNCTION (1)
SUPERMODULAR FUNCTION (1)
SYMMETRY (1)
SZEGED INDEX (1)
TRANSPOSITION GRAPHS (1)
TRIANGLE PATH CONVEXITY (1)
TRIANGLE-FREE GRAPH (1)
UNIMODALITY (1)
more

INFONA - science communication portal

Discrete Applied Mathematics

Neighbor sum distinguishing total choosability of planar graphs without 4-cycles

On r-dynamic coloring of graphs

Contents

On the further relation between the (revised) Szeged index and the Wiener index of graphs

On Wiener and multiplicative Wiener indices of graphs

The maximum matching energy of bicyclic graphs with even girth

Detour trees

Intersection graphs of L-shapes and segments in the plane

On the extreme eccentric distance sum of graphs with some given parameters

Improving the characterization of P-stability for applications in network privacy

House-swapping with divorcing and engaged pairs

On the geodetic iteration number of the contour of a graph

Largest domination number and smallest independence number of forests with given degree sequence

Complexity aspects of the triangle path convexity

Disjoint Hamilton cycles in transposition graphs

On the uniqueness of some girth eight algebraically defined graphs

Pattern restricted Stirling k-ary words, the plateau statistic and the kernel method

On del-robust primitive words

Dynamic coloring of graphs having no K5 minor

Clique cover products and unimodality of independence polynomials

Filter options

Publication date

Number

Keywords

INFONA - science communication portal

Discrete Applied Mathematics

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Number

Keywords

Reporting an error / abuse

Sending the report failed

Accessibility options